Calculate complexity for simple algorithm using summations

Question

I want to calculate exact bounded complexity (theta) for the following simple loop system

for i = 1 to n do
   for j = i to 2i do
       for k = j to 2j do
          ...

I know I can calculate theta with nested summations, using one for each loop. However, i am unsure as to what the ranges on those summations should be.

My instinct tells me I should use 1 ...n, 1...2n, 1...4n. Is this fine or would this represent an upper bound? Should it be 1...n, 1...i, 1...j for the lower bound? should the ranges be separated into disjoint sets for this analysis?

please just help me define the ranges for the summations with an explanation as to why it should be that way :(

thank you!

Answer 1

Assuming inside of third loop takes constant time $c$ then running the whole algorithm takes:

$$T(n) = \sum_{i = 1} ^ {n} \sum_{j = i} ^ {2 i} \sum_ {k = j} ^ {2 j} c$$

Summation limits are exactly same as in the loops. We can then calculate $T(n)$ : $$ \begin{aligned} T(n) &= c\sum_{i = 1} ^ {n} \sum_{j = i} ^ {2 i} (2j - j + 1) \\ \\ & \vdots \text{ (left as an exercise)} \\ \\ &= \frac{c} {2}(n^3+4 n^2+5n) \end{aligned}$$

So $T(n) = \Theta(n^3)$

Answer 2

For $\theta(n)$ of the time of the first loop, $i$ is $\theta(n)$. (Think about the second half of this loop when $i>\frac{n}{2}$.)

In this time, for $\theta(i)=\theta(n)$ of the time of the second loop, $j$ is $\theta(i)=\theta(n)$.

In this time, for $\theta(j)=\theta(i)=\theta(n)$ of the time of the second loop, $k$ is $\theta(j)=\theta(i)=\theta(n)$.

Hence for most of the time, the first loop is ran $\theta(n)$ times, the second loop is ran $\theta(n)$ times and the third loop is also ran $\theta(n)$ times, making the algorithm $\theta(n^3)$.