O(n) of given code 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?
 A: 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)
$$
A: 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.
A: 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)$.
A: 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$.
