Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
  1. How can I describe the growth function in terms of n for the following algorithm?
  2. What is the bounding function (the Big-O)? Is it O(n^3)?

for(i = 0 to n - 1)
{
    c = i + 1
    for(j = c to n)
    {
        arr[j] += arr[i];

        for(k = c to 0 step -1) // what does the keyword "step" mean?
        {
            arr[k] *= arr[j];
        }
    }
}
share|improve this question

migrated from stackoverflow.com Aug 2 '13 at 20:18

This question came from our site for professional and enthusiast programmers.

    
Step means that you are decrementing. step 1, is assumed in the other for declarations. Since this time we're counting down, step -1 is specified. –  ChrisCM Jul 26 '13 at 19:26
    
I answered a three loop puzzle of this type here may be you find helpful –  Grijesh Chauhan Jul 26 '13 at 19:28
    
ohhh. So that's why the "normal" i++ increment is not here. The innermost for is k--? –  positiveimpact Jul 26 '13 at 19:28
1  
yah, it's O(N^3) –  Fallen Jul 26 '13 at 19:29
    
So I have to find a closed formula for n? –  positiveimpact Jul 26 '13 at 19:30

4 Answers 4

up vote 3 down vote accepted

This is the rule in general :

for k nested loop you will have O(n^k) in the below case you will have O(n^3)

for(i = 0 to n - 1)
{
    c = i + 1
    for(j = c to n)
    {
        arr[j] += arr[i];

        for(k = c to 0 step -1) // what does the keyword "step" mean?
        {
            arr[k] *= arr[j];
        }
    }
}

For k loops next to each other you will have kxO(n) which comes back to O(n)

like below :

       for(k = c to 0 step -1) // what does the keyword "step" mean?
        {
            arr[k] *= arr[j];
        }
       for(k = c to 0 step -1) // what does the keyword "step" mean?
        {
            arr[k] *= arr[j];
        }
       for(k = c to 0 step -1) // what does the keyword "step" mean?
        {
            arr[k] *= arr[j];
        }

you have O(3xn) which is O(n)

You can also read this: Finding Big-O with multiple nested loops?

share|improve this answer
    
So the inner-most loop is O(n). But, why does this mean that the whole algo. is O(n^3)? I made a good guess, but I'm still not sure why. I see your statement that it's O(n^3), but why is it n^k? –  positiveimpact Jul 26 '13 at 19:43
1  
I don't believe that it is in fact O(n^3), this line of logic is ignoring the (c=i+1) line, which is very much diminishing the amount of work the inner loops need to do. I am working on an answer. I believe the tightest bounding function is actually O(n^2) –  ChrisCM Jul 26 '13 at 19:44
    
@ChrisCM: for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)for(int k=0;k<i;k++) what should be the complexity for these three loops? ;-) –  Fallen Jul 26 '13 at 19:47
1  
@Fallen it is n x n/2 x n/2 I think but still considered as O(n^3) –  Mehdi Karamosly Jul 26 '13 at 19:53
1  
But I believe you're correct, the tightest bound is n^3/4, which is O(n^3) –  ChrisCM Jul 26 '13 at 20:07

The question is about complexity but first, I was curious to know if I could compute the number of times this algorithm is doing the multiplication.

The 2 last inner loops are doing c * (n - c) iterations. This is equal to nc - c².

The very first loop make the total number of iterations: sum(c=1 to n) of (nc - c²)

sum(c=1 to n) of (nc - c²)
= n*sum(c=1 to n) of c - sum(c=1 to n) of c²
= n*(n² + n) / 2 - (2n³ + 3n² + n) / 6
= (n³ - n) / 3

So the number of iterations is (n³ - n) / 3 (answer to Q.1). And the complexity is then O(n³) (answer to Q.2).

share|improve this answer

I agree with the already posted answers. However, I would like to present an alternative way of obtaining an asymptotic lower bound without having to obtain the closed form.

Consider only cases of n>100. For over n/4 iterations, c is both greater than n/3 and less than 2n/3. Each of those iterations of the outer loop does at least n/3 iterations of the middle loop, each of which does at least n/3 iterations of the innermost loop. Thus the total number of innermost loop iterations is at least (n/4) * (n/3) * (n/3).

The number of innermost loop iterations is bounded above by n^3, because each of the three nested loops does no more than n iterations.

A function that is bounded below by (n^3)/36 and above by n^3 is Theta(n^3).

share|improve this answer

It is clearly O(n^3), since it involves three loops. And for every loop you have, upper bound of times is 'n'(even the innermost loop), because it doesn't involve constant in any loop. Hence it is n^3 solution.

I have written a dummy count program to verify the same

    int count = 0;
    for(int i = 0; i < 100; i++) {
        int c = i + 1;
        for (int j = c; j < 100; j++) {
            for(int k= c; k >= 0; k--) {
                count ++;
            }
        }
    }
share|improve this answer
1  
Not every triply nested loop is O(n^3). The lower bound can effect the big-O a lot. –  Andrew Piliser Jul 26 '13 at 19:48
1  
who is voting this down? this answer is correct. It is O(n^3). That it is maybe also O(n^2) doesn't contradict this, O(n^2) is included in O(n^3). –  Jens Gustedt Jul 26 '13 at 20:55
4  
your calculation is correct. Downvote for this line, It is clearly O(n^3), since it involves three loops. –  Fallen Jul 26 '13 at 21:57
1  
@Fallen As long as each of the three loops has an iteration count that is bounded above by a linear function of n, it must be O(n^3). It may also be O(n^2), or less, depending on the loop ranges. Big-O notation is only an upper bound. –  Patricia Shanahan Jul 27 '13 at 14:01
1  
@Fallen I agree that the complexity of a loop can vary. I'm stating a condition: if each of the three nested loops has iteration count bounded above by a linear function of n then the innermost code is executed O(n) times. Note that Big-O is only an upper bound. The constant function f(n)=0 is O(n^3). –  Patricia Shanahan Jul 27 '13 at 15:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.