O(n) of given code

Question

sum = 0
for (i = 0; i < n; i++)
    for (j = 0; j < i * i; j++)
        for(k = 0; k < n; k++)
            ++sum

Here is my work

The outer most loop:

$$ \sum_{i}^{n} $$ The first inner loop: $$ \sum_{j}^{i^2} $$ The second inner loop: $$ \sum_{k}^{n} $$ So I end up with: $$ \sum_{i}^{n}\sum_{j}^{i^2}\sum_{k}^{n} \\ \sum_{i}^{n}\sum_{j}^{i^2}n\\\sum_{i}^{n}\frac{j^2(j^2+1)}{2}\\ $$

From that I get that the complexity is $O(n^8)$. Am I correct?

Answer 1

I cannot see the code, please paste the text into the question instead of the picture. The last step looks incorrect. Simplify $$ \sum_{j=1}^n j^2(j^2+1) = \sum_{j=1}^n j^4 + \sum_{j=1}^n j^2, $$ and the first term is $\Theta(n^5)$ while the second is $\Theta(n^3)$, so the sum is $$\Theta(n^5)+\Theta(n^3)=\Theta(n^5).$$

UPDATE

Now you have $$ \sum_{i=1}^n \sum_{j=1}^{i^2} \sum_{k=1}^n 1 = \sum_{i=1}^n \sum_{j=1}^{i^2} n = n \sum_{i=1}^n \sum_{j=1}^{i^2} 1 = n \sum_{i=1}^n i^2 = n \frac{n(n+1)(2n+1)}{6} = \Theta\left(n^4\right) $$

Answer 2

The inner loop is traversed $n$ times per traversal of the middle loop. The middle loop is traversed $i^2$ times for each $i$ through which the outer loop goes. The outer loop makes $i$ go from $1$ to $n$. The middle loop is therefore traversed $\sum_{i=1}^n i^2$ times which is $O(n^3)$. Thus, the total time -- i.e., the number of times the inner loop is traversed -- is $O(n^4)$. (Actually, $\Theta(n^4)$.) Now, this assumes that the complexity for incrementing the variable sum is constant.

Answer 3

Fix a value of $i$. There are $i^2$ values of $j$, and for each of them the innermost loop is executed $n$ times, so the ++sum is executed $i^2n$ times for that value of $i$. Thus, you want

$$\sum_{i=1}^ni^2n=n\sum_{i=1}^ni^2=n\cdot\frac{n(n+1)(2n+1)}6=\frac16n^2(n+1)(2n+1)\;,$$

which is $O(n^4)$.

By the way, a useful general fact is that $\sum_{k=1}^nk^r$ is $O(n^{r+1})$, so your final incorrect summation would actually be $O(n^5)$, not $O(n^8)$.

Answer 4

Reading from inside to outside:

        for(k = 0; k < n; k++)
            ++sum

$$ s^n(0) $$ where $s(i) = i + 1$ and $s^n(0) = n$.

    for (j = 0; j < i * i; j++)

$$ (s^n)^{i^2}(0) = s^{i^2 n}(0) $$

for (i = 0; i < n; i++)

$$ S = s^{\sum_{i=0}^{n-1} i^2 n}(0) = s^{n \sum_{i=0}^{n-1} i^2}(0) = s^{n \frac{2(n-1)^3+3(n-1)^2+(n-1)}{6}}(0) = n\frac{2(n-1)^3+3(n-1)^2+(n-1)}{6} $$ So this is just a not efficient way, $O(n^4)$ applications of the successor function $s$, to compute the above value $S$.