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];
        }
    }
}
15
  • 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, 2013 at 19:26
  • I answered a three loop puzzle of this type here may be you find helpful Jul 26, 2013 at 19:28
  • ohhh. So that's why the "normal" i++ increment is not here. The innermost for is k--?
    – positiveimpact
    Jul 26, 2013 at 19:28
  • 1
    yah, it's O(N^3)
    – Fallen
    Jul 26, 2013 at 19:29
  • So I have to find a closed formula for n?
    – positiveimpact
    Jul 26, 2013 at 19:30

4 Answers 4

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

10
  • 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, 2013 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, 2013 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, 2013 at 19:47
  • 1
    @Fallen it is n x n/2 x n/2 I think but still considered as O(n^3) Jul 26, 2013 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, 2013 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 ++;
            }
        }
    }
7
  • 1
    Not every triply nested loop is O(n^3). The lower bound can effect the big-O a lot.
    – Andrew Piliser
    Jul 26, 2013 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). Jul 26, 2013 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, 2013 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. Jul 27, 2013 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). Jul 27, 2013 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.