worst case running time calculation

10,972

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

Solution 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

Solution 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:

enter image description here

Share:
10,972
shengy
Author by

shengy

Likes: C/C++, Go, Python, git, vim, linux, mac

Updated on June 15, 2022

Comments

  • shengy
    shengy over 1 year

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

  • Petar Ivanov
    Petar Ivanov about 11 years
    his answer is a heuristic, that might work, in most cases, but is a wrong argument - the inner loop doesn't run N^2 times of course. And you can't just multiply the inner and the outer loops as if they were independent
  • shengy
    shengy about 11 years
    So can I conclude that if the outer loop and the inner loop is independent, I can simply multiply their run times, such as O(m*n), but if they are not independent, I can only analysis it by hand and figure something like when i=0, inner loop will run x times and then add them together and find a sum formula?
  • Petar Ivanov
    Petar Ivanov about 11 years
    yeah exactly - when they are independent you can of course multiply. It's all a matter of how many times the inner loop runs - that's all it matters
  • shengy
    shengy about 11 years
    Or can I substitute vars in the inner loop like kpentchev did in his answer?
  • Petar Ivanov
    Petar Ivanov about 11 years
    So by substituting i with sqrt(N), you actually didn't prove the complexity to be O(N^(3/2)). You only prove that the complexity is <= O(N^(3/2)). Because what you are doing is you are bounding it from above.
  • Petar Ivanov
    Petar Ivanov about 11 years
    The substitution only works to show that the complexity is not more than O(N^(3/2)). He still has no guarantee that the complexity is not lower than that. And in general you can't just substitute stuff here and there. You have to explain why you can substitute and what that means in each case.
  • shengy
    shengy about 11 years
    Got it, so there are no silver bullets in calculating the worst time... Have to do it in hand eventually.
  • shengy
    shengy about 11 years
  • kpentchev
    kpentchev about 11 years
    I stand corrected. What I did is only valid for independent nested loops, which these are not. Your formula is correct.