The order of growth as the worst-case run time as a function of N

Question

Given the following code snippet:

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

My suggestion:

• Outer cycle: O (N)
• Middle loop: O (N * N)
• Inner loop: O (N * N)

Therefore, the total runtime should be O (N ^ 5), right?

Answer 1

Preliminary note

 sum(k=1,p,k^2) = p(p+1)(2p+1)/6 = O(p^3) sum(k=1,p,k^6) = O(p^7) 

Difficulty calculation

• The innermost loop runs from k=1 to j^2 , so it performs operations j^2 .
• The middle cycle runs from j=1 to i^2 , and at each step we perform operations j^2 . According to my preliminary observation, substituting p=i^2 in the first equation, we can calculate the complete operations as: i^2(i^2+1)(2*i^2+1)/6 for each value of i . This number of operations is O((i^2)^3) = O(i^6) .
• The outer loop runs from i=1 to n and performs O(i^6) operations at each step. So, we have operations O(n^7) .

References

• http://www.math.com/tables/expansion/power.htm

Answer 2

Allows you to open how many times each cycle will be executed.

 First loop 1, 2, 3, 4, 5, ...., N Second loop 1, 4, 9, 16, 25, ...., (N*N) // N^2 Third loop 1, 16, 81, 256, 625, ...., ( (N*N)*(N*N) ) // N^4 

So, I believe that complexity should be N ^ 4

EDIT 1

Based on the comment, I think the complexity will be the sum of the series

 1, 16, 81, 256, 625, ...., ( (N*N)*(N*N) ) 

EDIT 2

I think we made a mistake when opening loops (thanks to CodeYogi ). Let's try again.

 First loop 1, 2, 3, 4, 5, ...., N Second loop 1, 4(1,2,3, 4), 9 (1,2,....9), 16, 25, ...., (N*N) Third loop 1, 30(1+4+9+16), 285(1+4+...81), and so on.......... 

Answer 3

I think the final O is definitely higher than O(n^4) and slightly higher than O(n^5) , but since this is Big O notation, we can say that it is O (n ^ 5) . The last loop will execute this number of times:

 1 + 2^4 + 3^4 + 4^4 + ... + n^4 

Wolframalpha presents it as:

Note the extended version for n>0 :

Edit:

I just realized that there is a gap in my answer, because most of the inner loops will execute more times than I expected. Looking at the results of this triple loop and striking through it, it seems to be higher than O(n^6) . Let's get back to that.

Edit 2: As I said, I was wrong. Can't explain it better than @fjardon's answer.