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