Big-Oh of nested loops, where inner loop depends on i*n and i*i of outer loop

Question

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!

Answer 1

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:

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:

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