$f \in O(\log(n))$?

Question

How can I find the complexity of

i = 1;
while( i <n)
{
 i = 2*i;
}

using summation?

I have $f(n) = \sum_{i=1, i=2*i}^{n-1}1$, but I am not sure how to solve that. I think $f \in O(\log(n))$

score 1 · Answer 1 · answered Jan 28 '21 at 20:33

1

In your while-loop $i$ increases exponentially.

On the $k^{th}$ iteration, you have $i= 2^{k}$ and will end when $2^k\ge n$.

So, the loop will exit as soon as $k\ge \log_2(n)$.

answered Jan 28 '21 at 20:33

David P

Can you developpe a bit more? So I was right to say $f \in O(\log(n))$, right? I would need to prove it rigorously – Alex Jan 28 '21 at 21:37
I think I was rigorous? And as far as $f\in O(\log(n))$, The number of iterations $k$ satisfies $k<\log_2(n) = \dfrac{1}{\ln(2)}\cdot \ln(n)$. The value of $c$ is $1/\ln(2)$ for $f\le c\cdot \log$, assuming by $\log$ you mean the natural log, though it doesn't really matter. – David P Jan 29 '21 at 03:08

1 Answers1