Calculation of the worst working hours

Question

This is from homework, but I ask for a general method.

Calculate the worst-case code run time.

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

answer N ^ 3/2, can someone help me with 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 

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

Answer 1

You want to count how many times the innermost loop will execute.

External will work from i = 0 to i = sqrt (N) (since I * i <N). For each iteration of the outer inner it will be performed ^ 2 times.

Thus, the total number of times that will be executed internally 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 is the total complexity O(sqrt(N)^3) = O(N^(3/2)) .

Answer 2

You are approaching this problem incorrectly. To calculate the worst time, you need to find the maximum number of operations that will be performed. Since you have only one operation in a double loop, it is enough to find out how many times the inner loop will be executed.

You can do this by exploring the limits of your cycles. For the outer loop, this is:

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

The limit for your inner cycle

 j < i^2 

You can replace at the second equator to get j < N .

Since these are nested loops, you multiply your limits to get the final result:

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

Answer 3

then just calculate this amount

(i ^ 2) / 2 * N ^ (1/2) = N / 2 * N ^ (1/2) = N ^ (3/2)

Answer 4

Your algorithm can be converted into the following form:

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

Therefore, we can directly and formally do the following: