0

What is the Big-Oh of the following nested loops:

sum=0;
for(i=0;i<n;i++)
    for(j=0;j<i*n;j++)
        sum+=i;

and

sum=0;
for(i=0;i<n;i++)
    for(j=0;j<i*i;j++)
        sum+=i;

I believe it's O(n^2), but all I've ever encountered is both loops using n as the test, so I don't know if O(n^2) is correct. If someone could verify my understanding or explain why I'm wrong, I'd appreciate it. Thanks!

user2864740
  • 60,010
  • 15
  • 145
  • 220
flaw600
  • 161
  • 1
  • 2
  • 8
  • possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Michael Robinson Sep 08 '14 at 00:16
  • That question asked how to approximate in general. Here, I believe I know the approximation but I want to check my answer, and if it's wrong, understand why. That question doesn't have an answer for nested loops in particular – flaw600 Sep 08 '14 at 01:11

1 Answers1

4

I would say that they are both O(n^3), since in both cases the inner loop is O(n^2) and the outer loop is O(n). Granted they will run much much less than n^3 times, but if you graphed the runtime as a function of n, as n gets huge, you would find that the shape looks more like a cubic than a quadratic. My proof is that if you unroll the sum for the first one you get:

equation1

since you have n terms, each of which is O(n^2), the whole thing is O(n^3), albeit a very small O(n^3).

For the second one:

enter image description here

which is even smaller than the first one, but still O(n^3).

Mike Ounsworth
  • 2,444
  • 21
  • 28
  • That makes sense. Thanks! So is the general rule for nested loops for Big-O, the inner * outer? From what I understand of your explanation and what my book said (it said it in a very confusing way, and thus why I wasn't able to understand the above 2 algorithms), that seems to be the case, but I just want to confirm. Thanks! – flaw600 Sep 08 '14 at 01:08
  • Yes! The general rule for big-O on loops is inner * outer. In equations you take the highest power of n and throw away everything else. – Mike Ounsworth Sep 08 '14 at 01:11
  • Just a quick additional question: is there a way to make the inner loop be O(n^3) w/o creating another loop? That is, with only 2 loops. – flaw600 Sep 08 '14 at 01:32
  • Sure, in the same way it's O(n^2) above: for( int j=0; j – Mike Ounsworth Sep 08 '14 at 01:35