# Finding growth rate of T(n) of a code segment

I am presented with the following code segment and asked to find the growth rate, which can be done by finding the number of times the variable sum is incremented:

sum = 0
for i = 1 to 2 * n
for j = 1 to i * i
for k = 1 to j
sum++


I tried making this into a function called run(n) in Python that returns sum and got run(1) = 11, run(2) = 192, run(3) = 1183, and run(4) = 4488. However, my book only presents 3 possible answers, those being $$\Theta(n^4)$$, $$\Theta(n^5)$$, and $$\Theta(n^6)$$.

I don't think my results match any of these choices. I might be confused as to what the question is asking as it says

present answers in terms of summations

or my code might be incorrect, but I am confused on what to do next. I am very new to algorithms, so any help would be appreciated.

The innermost loop increments sum exactly $$j$$ times. The middle loop runs $$i^2$$ times with increasing values of $$j$$ so it increments sum $$\dfrac{i^2(i^2+1)}2$$ times. And finally, the outer loop runs $$2n$$ times, for a total of $$\sum_{i=1}^{2n}\frac{i^2(i^2+1)}2=\frac{n (1 + 2 n) (1 + 4 n) (2 + 3 n + 6 n^2)}{15}$$ incrementations. [Thanks to Wolfram Alpha.]

Let $$I$$ be the number of times the for i is executed, $$J$$ the number of times for j, and $$K$$ the number of times for k is executed.

1. $$I$$ is $$\Theta(n)$$ times
2. $$J$$ is $$\Theta(I \cdot I) = \Theta(n^2)$$ times
3. $$K$$ is $$\Theta(J) = \Theta(n^2)$$

The correct answer is the product of $$I$$, $$J$$ and $$K$$, i.e., $$\Theta(n \cdot n^2 \cdot n^2) = \Theta(n^5)$$.

• That was a very clear explanation, thank you! Commented Sep 26, 2023 at 9:27
• Caution, this method can lead to false results. Take an outer loop for $i$ from $1$ to $n$, and inner loop from $1$ to $2^i$. You would say $\Theta(n)\cdot\Theta(2^n)=\Theta(n\cdot2^n)$ though the correct answer is $\Theta(2^n)$.
– user16034
Commented Sep 26, 2023 at 9:56