# Complexity of an algorithm

I tried to solve the following exercise :

What is the order of growth of the worst case running time of the following code fragment as a function of N?

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++;


and I found that the complexity is O(n^4), however the correct answer is :

For a given value of i, the body of the innermost loop is executed 1^2 + 2^2 + 3^2 + ... + (i^2)^2 ~ 1/3 i^6 times. Summing up over all values of i yields ~ 1/21 N^7.

I would like some help to understand this answer and the correct way to calculate complexity in this case.

• What don't you understand in the explanation given? – ruler501 May 2 '15 at 19:57
• For many reasons, for example, for me 1^2 + 2^2 + 3^2 + ... + (i^2)^2 ~i^4 but I must be wrong – Neo May 2 '15 at 20:09
• $1^k + 2^k + 3^k + \dots + n^k = \Theta(n^{k+1})$, so putting $n=i^2$ and $k=3$ gives $\Theta(n^6)$. – David Richerby May 3 '15 at 0:32
• possible duplicate of Is there a system behind the magic of algorithm analysis? – David Richerby May 3 '15 at 0:35

int I(int n) { for (i = 1; i <= n; i++) J(i); }

Instead of measuring time complexity, let us use instead the number of times sum is incremented as our complexity measure. Also, let $I(n),J(n),K(n)$ double as the complexity of the functions with matching name.
It is not hard to see that $K(n) = n^2$. Therefore $$J(n) = \sum_{j=1}^{n^2} K(j) = \sum_{j=1}^{n^2} j^2.$$ Now we invoke the formula $\sum_{j=1}^m j^2 \sim m^3/3$. Substituting $m = n^2$, we get $$J(n) \sim \frac{n^6}{3}.$$ Continuing, $$I(n) = \sum_{i=1}^n J(i) \sim \frac{1}{3} \sum_{i=1}^n i^6 \sim \frac{1}{21} n^7.$$ Some of these estimates are not completely rigorous, but you can make them rigorous with a bit of work.
• Wolphram Alpha gives us $\frac{n^7}{21}+\frac{n^6}{6}+\frac{4 n^5}{15}+\frac{n^4}{4}+\frac{n^3}{6}+\frac{n^2}{12}+\frac{2n}{105}$ – André Souza Lemos May 3 '15 at 4:43