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

The answer is : N^7

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? May 2, 2015 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, 2015 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)$. May 3, 2015 at 0:32
• possible duplicate of Is there a system behind the magic of algorithm analysis? May 3, 2015 at 0:35

## 1 Answer

It will be easier to analyze things if we break them down into several different procedures:

int I(int n) { for (i = 1; i <= n; i++) J(i); }
int J(int n) { for (j = 1; j <= n*n; j++) K(j); }
int K(int n) { for (k = 1; k <= n*n; k++) sum++; }

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}$ May 3, 2015 at 4:43