Asymptotic calculation check for triple-nested for-loops

Question

I have the following repetition structure:

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

By the following, I have reasoned the runtime of this structure to be in $O(n^7)$ :

$\sum_{i=1}^{n} (\sum_{j=1}^{i^2}(\sum_{k=1}^{j} k))$

$= \sum_{i=1}^{n}(\sum_{j=1}^{i^2}(\frac{j^2+j}{2}))$

$= \frac{1}{2} (\sum_{i=1}^{n}(\sum_{j=1}^{i^2}j^2 + \sum_{j=1}^{i^2}j))$

$= \frac{1}{2} (\sum_{i=1}^{n}(\frac{i^2(i^2+1)(2i^2+1)}{6} + \frac{i^2(i^2+1)}{2}))$

$= \frac{1}{2} (\sum_{i=1}^{n} \frac{2i^6+3i^4+i^2}{6} + \sum_{i=1}^{n} \frac{i^4+i^2}{2})$

$= \frac{1}{2} (\frac{1}{3} \sum_{i=1}^{n} i^6 + \frac{1}{2} \sum_{i=1}^{n} i^4 + \frac{1}{6} \sum_{i=1}^{n} i^2 + \frac{1}{2} \sum_{i=1}^{n} i^4 + \frac{1}{2} \sum_{i=1}^{n} i^2)$

$=\frac{1}{6} \sum_{i=1}^{n} i^6 + \frac{1}{2} \sum_{i=1}^{n} i^4 +\frac{1}{3} \sum_{i=1}^{n} i^2$

$\approx \frac{n^7}{42} + \frac{n^5}{10} + \frac{n^3}{9}$

$\therefore \text{runtime} \in O(n^7)$

The approximation at the end comes from the rule:

$\sum_{i=1}^{n} i^k \approx \frac{n^{k+1}}{k+1}$

Is this correct? I'm fairly confident that it is but some of the results that I've gotten from running the structure in JMH (Java Micro-Benchmarking Harness) don't really reflect this result so I just want to confirm.

Answer 1

The inner loop always executes sum++ $j$ times. The middle loop lets $j$ vary from $0$ to $i^2-1$, so the count equals $\dfrac{(i^2-1)\,i^2}2$. The outer loop runs for $i$ from $0$ to $n-1$ hence

$$\sum_{i=0}^{n-1}\dfrac{(i^2-1)\,i^2}2\sim\frac{n^5}{10}.$$

---

There is no real need to give a more accurate expression, as you should account for the other statements anyway.

Answer 2

As Yuval Filmus and gnasher729 have pointed out my original equation for the repetition structure is indeed wrong. I believe this to be the true correct answer:

$\sum_{i=1}^{n} (\sum_{j=1}^{i^2} j)$

$= \sum_{i=1}^{n} (\frac{i^4+i^2}{2})$

$= \frac{1}{2} \sum_{i=1}^{n}i^4 + \frac{1}{2} \sum_{i=1}^{n}i^2$

$\approx \frac{n^5}{10} + \frac{n^3}{6}$

$\therefore runtime \in O(n^5)$