worst case running time calculation

Question

It's from homework, but I'm asking for a general method.

Calculate the following code's worst case running time.

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

the answer is N^3/2, could anyone help me through this?

Is there a general way to calculate this?

This is what I thought:

when i = 0, sum++ will be called 0 time
when i = 1, sum++ will be called 1 time
when i = 2, sum++ will be called 4 times
...
when i = i, sum++ will be called i^2 times

so the worst time will be
0 + 1 + 4 + 9 + 16 + ... + i^2

but what next?? I'm lost here...

Answer 1

You want to count how many times the innermost cycle will run.

The outer one will run from i = 0, to i = sqrt(N) (since i*i < N). For each iteration of the outer one the inner one will run i^2 times.

Thus the total number of times the inner one will run is:

1^2 + 2^2 + 3^2 + ... + sqrt(N)^2

There is a formula:

1^2 + 2^2 + ... + k^2 = k(k+1)(2k+1) / 6 = O(k^3).

In your case k = sqrt(N).

This the total complexity is O(sqrt(N)^3) = O(N^(3/2)).

Answer 2

You are approaching this problem in the wrong way. To count the worst time, you need to find the maximum number of operations that will be performed. Because you have only a single operation in a double loop, it is enough to find out how many times the inner loop will execute.

You can do this by examining the limits of your loops. For the outer loop it is:

i^2 < N => i < sqrt(N)

The limit for your inner loop is

j < i^2

You can substitute in the second equasion to get j < N.

Because these are nested loops you multiply their limits to get the final result:

sqrt(N)*N = N^3/2

Answer 3

Your algorithm can be converted to the following shape:

int sum = 0;
for (int i = 0; i < Math.sqrt(N); i++)
    for (int j = 0; j < i*i; j++)
        sum++;

Therefore, we may straightforwardly and formally do the following: