Analyzing the time complexity of nested loops

Question

So I've been given a piece of pseudo code that involves nested loops. The answer to this question is Θ(n^5) but I do not understand why it is so.

What is the time complexity of this code?

for  i = 1 to n   
   for  j = 1 to n*n    
      for  k = 1 to j     
         Task  


where the time complexity of Task is Θ(1)

The most inner loop, for k = 1 to j is Θ(j). Then the middle loop, for j = 1 to n^2 I thought, should produce Θ(n^2) as it loops from j = 1 to n^2 but I've been told it's Θ(n^4). I honestly do not understand how it could be Θ(n^4) when it's iterating from 1 to n^2. Can someone explain how this works in simple terms?

Answer 1

You are correct: the middle loop executes $\Theta(n^2)$ inner loops.

What you are told is correct: the runtime of the middle loop is $\Theta(n^4)$.

Your mistake is confusing the two. The inner loop does not run in constant time, so you should not expect the middle loop to complete in $\Theta(n^2)$ time. You can, however, expect the middle loop to complete in

$$ \sum_{j=1}^{n^2} \Theta(j) = \Theta\left( \sum_{j=1}^{n^2} j \right) = \Theta(n^4)$$

time. (and with care, you can even make this calculation rigorous!)

You could heuristically guess that enough loop iterations take close enough to maximum time and guess the middle loop would take $n^2 \cdot \Theta(n^2)$ time, although this heuristic can go astray.

However, the heuristic can also be made rigorous -- e.g. by determining $\Theta(n^2)$ of the loop iterations will complete in half of the maximum time, or by determining that the last half of the loop iterations each take $\Theta(n^2)$ time.

Answer 2

Translating for-loops into sums is the best way to approach this as the resulting calculations are elementary. We get:

$\qquad\displaystyle\begin{align*} \#\mathrm{Task} \quad&= &&\sum_{i=1}^n \sum_{j=1}^{n^2} \sum_{k=1}^j 1 \\ &= && \sum_{i=1}^n \sum_{j=1}^{n^2} j \\ &= && \sum_{i=1}^n \frac{n^2(n^2 + 1)}{2} \\ &= && \frac{n^3(n^2 + 1)}{2}. \end{align*}$

We use the closed form of the triangular numbers (which you find on any formulary if you have not memorized it). Finally, obtain a $\Theta$-class using standard tools.

Answer 3

For each value of $i$, the number of times that "task" is run is $$ \sum_{j=1}^{n^2} \sum_{k=1}^j 1 = \sum_{j=1}^{n^2} j. $$ The latter sum is at least $$ \sum_{j=1}^{n^2} j \geq \sum_{j=n^2/2}^{n^2} n^2/2 \geq (n^2/2)^2 = \Omega(n^4). $$ It is also plainly at most $(n^2)^2 = O(n^4)$.