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. Mar 26, 2020 at 12:31
• I’ve got a different power. Second line is wrong. Mar 26, 2020 at 13:49
• Can you clarify what's wrong in the Second line? Mar 26, 2020 at 19:25
• Actually the first line is already wrong. Mar 26, 2020 at 20:44
• You were tricked by the sum++ statement. It takes constant time hence the inner loop counts for $j$, not for the sum until $j$. Apr 16, 2022 at 14:28

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.

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

• That looks about right. Easiest way to check is to run this for n = 1 to 100, for each n count the number of iterations for k, and print out the results. n = 100 will take a while, but you can speed it up because you know the inner loop runs exactly j times. Aug 15, 2022 at 16:58
• @gnasher729: empirical evaluation is a very poor method. The timings usually have high variance plus different sources of bias, and you can very well miss slowly varying factors. Dec 12, 2022 at 12:57
• Empirical evaluation works very well most of the time. In this case it's obvious that it is some polynomial, with a leading coefficient that is a bit hard to figure out, with very little variation. Dec 12, 2022 at 15:30