Complexity using big-Oh notation

This is a discussion on Complexity using big-Oh notation within the C Programming forums, part of the General Programming Boards category; What is the worst case running time, in big-Oh notation, of the following program? Code: int function(int n) { r=0; ...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    31

    Complexity using big-Oh notation

    What is the worst case running time, in big-Oh notation, of the following program?

    Code:
    int function(int n)
    {
       r=0;
    
       for (i=1; i<n; i++)
          for (j=i+1; j<n+1; j++)
            for (k=1; k<=j; k++)
              r++;
       return r;
    
    
        return 0;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I feel confident that this is O(n! n^n e^n). You can probably come up with a sharper estimate, though, if you try.

    (I.E. and in other words: show some effort and we will look more kindly upon the question.)

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    31
    Quote Originally Posted by tabstop View Post
    I feel confident that this is O(n! n^n e^n). You can probably come up with a sharper estimate, though, if you try.

    (I.E. and in other words: show some effort and we will look more kindly upon the question.)
    I''ve tried to calculate it...
    My answer was O(n^2)

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If the result was O(n^2), and using the fact that the outer loop goes from 1 to n, that would suggest that the inner two loops together execute in O(n). Does that seem possible?

  5. #5
    Registered User
    Join Date
    Mar 2010
    Posts
    31
    Quote Originally Posted by tabstop View Post
    If the result was O(n^2), and using the fact that the outer loop goes from 1 to n, that would suggest that the inner two loops together execute in O(n). Does that seem possible?
    I took it step by step
    for i=1
    first loop o(1), second o(n-1), third o(2)*o(2)*...*o(n) ---> that is o(n*n!)
    for i=2
    first loop o(1), second o(n-2), third o(3)*...*o(n)
    and so on

    for i=n-1
    first loop o(1) second o(1), third o(n)

    And then we add them.
    Is this how it works?

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    The first loop isn't O(1), it's O(j) -- more specifically, it's exactly j. So that means your second loop, you need to add up j as j goes from i+1 to n+1 (you should hopefully have a formula for that). Then that value gets added as i goes from 1 to n.

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by tabstop View Post
    I feel confident that this is O(n! n^n e^n). You can probably come up with a sharper estimate, though, if you try.
    How do you figure? No loop executes more than n times, so it can't be bigger than O(n^3)
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by brewbuck View Post
    How do you figure? No loop executes more than n times, so it can't be bigger than O(n^3)
    O is just an upper bound, so any algorithm that is O(n^3) is also O(n^4), and ..., and O(anything really big). (It's not helpful, but it's true.)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. big O notation question
    By l2u in forum C++ Programming
    Replies: 7
    Last Post: 11-08-2008, 02:53 PM
  2. about big O notation
    By deepakkrmehta in forum C Programming
    Replies: 3
    Last Post: 08-27-2005, 02:31 PM
  3. Big Oh notation, help me notate this
    By Jeremy G in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 05-12-2005, 03:27 PM
  4. big o notation
    By heat511 in forum C++ Programming
    Replies: 5
    Last Post: 04-19-2002, 11:27 AM
  5. Big O Notation
    By Drew in forum C++ Programming
    Replies: 1
    Last Post: 09-30-2001, 01:22 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21