worst case running time calculation
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:
Comments
-
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 about 11 yearshis 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 about 11 yearsSo 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 about 11 yearsyeah 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 about 11 yearsOr can I substitute vars in the inner loop like kpentchev did in his answer?
-
Petar Ivanov about 11 yearsSo 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 about 11 yearsThe 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 about 11 yearsGot it, so there are no silver bullets in calculating the worst time... Have to do it in hand eventually.
-
shengy about 11 years
-
kpentchev about 11 yearsI stand corrected. What I did is only valid for independent nested loops, which these are not. Your formula is correct.