1
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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.]

$\endgroup$
0
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ That was a very clear explanation, thank you! $\endgroup$
    – user163191
    Commented Sep 26, 2023 at 9:27
  • $\begingroup$ 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)$. $\endgroup$
    – user16034
    Commented Sep 26, 2023 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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