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.

$\endgroup$
  • 1
    $\begingroup$ What don't you understand in the explanation given? $\endgroup$ – ruler501 May 2 '15 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 May 2 '15 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 May 3 '15 at 0:32
  • $\begingroup$ possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$ – David Richerby May 3 '15 at 0:35
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.

$\endgroup$
  • $\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 May 3 '15 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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