World's most popular travel blog for travel bloggers.

# [Answers] Analyzing the time complexity of nested loops

, ,
Problem Detail:

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?

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.