Big-O of this algorithm?

Question

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];
 }
 }
}

• ChrisCM: 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.
• Grijesh Chauhan: I answered a three loop puzzle of this type here may be you find helpful
• positiveimpact: ohhh. So that's why the "normal" i++ increment is not here. The innermost for is k--?
• Fallen: yah, it's O(N^3)
• positiveimpact: So I have to find a closed formula for n?

Answer 1

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

• positiveimpact: 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?
• ChrisCM: 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)
• Fallen: @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? ;-)
• Mehdi Karamosly: @Fallen it is n x n/2 x n/2 I think but still considered as O(n^3)
• ChrisCM: But I believe you're correct, the tightest bound is n^3/4, which is O(n^3)

Answer 2

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

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

sum(c=1 to n) of (nc - c2)
= n*sum(c=1 to n) of c - sum(c=1 to n) of c2
= n*(n2 + n) / 2 - (2n3 + 3n2 + n) / 6
= (n3 - n) / 3

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

Answer 3

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

Answer 4

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

• Andrew Piliser: Not every triply nested loop is O(n^3). The lower bound can effect the big-O a lot.
• Jens Gustedt: 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).
• Fallen: your calculation is correct. Downvote for this line, It is clearly O(n^3), since it involves three loops.
• Patricia Shanahan: @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: @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).