0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Your code snippet seems to be working C code, so maybe you could try and experiment with it? $\endgroup$ – Laakeri Feb 2 at 13:55
  • 2
    $\begingroup$ Something else entirely. Somewhere in between your two guesses actually. $\endgroup$ – gnasher729 Feb 2 at 14:03
  • 2
    $\begingroup$ @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. $\endgroup$ – gnasher729 Feb 2 at 14:06
4
$\begingroup$

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)$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.