# Is this program O(n^2logn) or O(nlog^2(n))?

I was wondering whether this program (I'm using a C syntax, hope it's not an issue) is to be considered $$O(n^2 \log(n))$$ or $$O(n\log^2(n))$$ or something else entirely.

for(int i=0;i<n;i++)
for(int j=i; j>0; j/=2)
for(int k=j; k>0; k--)
printf("Hello, World!\n");


I mean, the innermost loop is for sure $$O(n)$$ but maybe it could have a tighter asymptotic upper bound? It executes a number of times that is dependent on a logarithmically decreasing value (j), so I'm not really sure how would I have to think about such a scenario.

• Your code snippet seems to be working C code, so maybe you could try and experiment with it? – Laakeri Feb 2 '20 at 13:55
• Something else entirely. Somewhere in between your two guesses actually. – gnasher729 Feb 2 '20 at 14:03
• @Laakeri An excellent idea. An experiment will give you an idea, and then you just need to figure out why that idea is correct and prove it. Trying to figure it all out in your head is often inefficient, when a little experiment can tell you. – gnasher729 Feb 2 '20 at 14:06

## 2 Answers

The complexity is $$O(n^2)$$. The reason is that the two inner loops take $$O(n)$$ time. The first iteration takes $$i$$ operations, then $$i/2$$, then $$i/4$$ until it's 0. So we need to compute the sum of $$i+i/2+i/4+...+1$$ operations which its upper bounded to $$2i$$. Finally because your outer loop is clearly $$O(n)$$ the total complexity is $$O(n^2)$$.

Suppose $$T(n)$$ is the time complexity of the above code. Then: $$T(n) = \sum_{i=0}^{n-1}(i + \frac{i}{2} + \frac{i}{4} + \cdots +‌ 1) =$$ $$\sum_{i=0}^{n-1}i (1 + \frac{1}{2} + \frac{1}{4} + \cdots +‌ \frac{1}{2^{\log(i)}})$$

As we know $$1 < 1 + \frac{1}{2} + \frac{1}{4} + \cdots +‌ \frac{1}{2^{\log(i)}} \leq 2$$:

$$\sum_{i=0}^{n-1} i = \frac{(n-1)n}{2} < T(n) \leq 2 \sum_{i=0}^{n-1} i = (n-1)n \Rightarrow T(n) = \Theta(n^2)$$

Hence, $$T(n) \in O(n^2\log(n))$$, too.