# Why does this triple loop code have a running time of 1.5lnN * N^2

Hi all, I'm currently going through the Princeton Algorithms course on coursera, and I'm having trouble understanding the answer to this quiz. I think I understand where the $$\frac{1}{2} N^2$$ term comes from, but I am completley lost on the $$3 \ln N$$ term. Unfortunatley this is the only solution.

• The factor 3 comes from the fact that it is accessing three times the array $a$ in line 5. – Marcelo Fornet Oct 11 '19 at 3:30

Let's consider the outer two loops first. For a fixed value of $$i$$, the number of iterations of the middle loop is exactly $$n-1 - (i+1) + 1 = n - i -1$$. Since $$i$$ ranges from $$0$$ to $$n-1$$ (in the outer loop), the overall number of iterations of the middle loop is: $$\sum_{i=0}^{n-1} (n - i -1) = \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}.$$

For each of those iterations we execute the inner loop for a certain number $$x \in \mathbb{N}$$ of iterations. Notice that $$x$$ only depends on $$n$$ and not on $$i$$ or $$j$$. Before the first iteration, the value of $$k$$ is $$1$$, and it doubles after every iteration (i.e., before the next iteration starts). This means that after a generic number $$h \in \mathbb{N}$$ of iterations (i.e., just before the $$(h+1)$$-th iteration starts) the value of $$k$$ is $$2^h$$. Since the loop continues as long as $$k = 2^h < n$$, we are interested in the minimum value of $$h$$ for which the above inequality is not true. This is $$x = \lceil \log n \rceil$$ if $$n \ge 1$$ (where we used the fact that $$h$$ must be a non-negative integer) and $$x = 0$$ otherwise. Since you are interested in the asymptotic behavior of the algorithm, I will ignore this latter case.

Finally, notice that for each iteration of the inner loop, exactly $$3$$ array accesses are performed.

To summarize:

• We reach the inner loop $$\frac{n(n-1)}{2}$$ times;
• Each time we perform $$\lceil \log n \rceil$$ iterations;
• Each iteration causes $$3$$ array accesses.

The total number of array accesses is therefore: $$\frac{3}{2}n(n-1) \lceil \log n \rceil \sim \frac{3}{2}n^2 \log n$$.