Order of growth as worst case running time as a function of N

 

Given the following code fragment: 

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

  • Outer loop: O(N)
  • Middle loop: O(N*N)
  • Innermost loop: O(N*N)

    • Hence, total running time should be O(N^5), right?

    A preliminary remark 

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

    Computation of complexity

  • The most inner loop runs from k=1 to j^2 so it does exactly j^2 operations.
  • The middle loop runs from j=1 to i^2 and at each step we do j^2 operations. According to my preliminary observation, by substituting p=i^2 in the first equation, we can compute the total operations as: i^2(i^2+1)(2*i^2+1)/6 for each value of i . This is an O((i^2)^3) = O(i^6) number of operations.
  • The outer loop runs from i=1 to n and does O(i^6) operations at each step. So we have O(n^7) operations.

    • References

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

    • Lets open up how many times every loop will run. 

    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 think the complexity should be N^4

    EDIT 1

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

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

    EDIT 2

    I think we made a mistake in opening the loops (Thanks to CodeYogi). Lets try one more time. 

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

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

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

    Wolframalpha represents it as:

    Please note expanded version for n>0 :

    Edit:

    I just realized, that there is a gap in my answer, cause most inner loop will be executed more times than I assumed. Looking at results of this triple loop and plotting it, it seems it is higher than O(n^6) . Will get back to it.

    Edit 2: As I mentioned, I was wrong. Cannot explain it better than @fjardon in his answer.

    链接地址: http://www.djcxy.com/p/87634.html

    上一篇: 流中的地图元素对应于帖子

    下一篇: 作为最坏情况运行时间的增长顺序是N的函数