1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What don't you understand in the explanation given? $\endgroup$
    – ruler501
    Commented May 2, 2015 at 19:57
  • $\begingroup$ For many reasons, for example, for me 1^2 + 2^2 + 3^2 + ... + (i^2)^2 ~i^4 but I must be wrong $\endgroup$
    – Neo
    Commented May 2, 2015 at 20:09
  • 1
    $\begingroup$ $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)$. $\endgroup$
    – David Richerby
    Commented May 3, 2015 at 0:32
  • $\begingroup$ possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$
    – David Richerby
    Commented May 3, 2015 at 0:35

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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}$ $\endgroup$
    – André Souza Lemos
    Commented May 3, 2015 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.