# Asymptotic calculation check for triple-nested for-loops

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.

• We typically don't verify proofs. We can help you if you are unsure about a particular step. – Yuval Filmus Mar 26 '20 at 12:31
• I’ve got a different power. Second line is wrong. – gnasher729 Mar 26 '20 at 13:49
• Can you clarify what's wrong in the Second line? – bmanicus131 Mar 26 '20 at 19:25
• Actually the first line is already wrong. – Yuval Filmus Mar 26 '20 at 20:44

## 1 Answer

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)$$