0
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ We typically don't verify proofs. We can help you if you are unsure about a particular step. $\endgroup$ Mar 26, 2020 at 12:31
  • 1
    $\begingroup$ I’ve got a different power. Second line is wrong. $\endgroup$
    – gnasher729
    Mar 26, 2020 at 13:49
  • $\begingroup$ Can you clarify what's wrong in the Second line? $\endgroup$ Mar 26, 2020 at 19:25
  • $\begingroup$ Actually the first line is already wrong. $\endgroup$ Mar 26, 2020 at 20:44
  • $\begingroup$ You were tricked by the sum++ statement. It takes constant time hence the inner loop counts for $j$, not for the sum until $j$. $\endgroup$ Apr 16, 2022 at 14:28

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Aug 15, 2022 at 16:58
  • $\begingroup$ @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. $\endgroup$ Dec 12, 2022 at 12:57
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Dec 12, 2022 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.