0
  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];
        }
    }
}
  • 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
3

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: https://stackoverflow.com/questions/766939/finding-big-o-with-multiple-nested-loops

  • 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
3

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).

2

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).

0

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 ++;
            }
        }
    }
  • 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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy