For $n \in \mathbb{N}$ how many times do I have to do this: $k=\lfloor \frac{n}{2} \rfloor$ till $k=1$?

For $n \in \mathbb{N}$ how many times do I have to do this: $k=\lfloor \frac{n}{2} \rfloor$ till $k=1$?

For example $11 \Rightarrow 5 \Rightarrow 2 \Rightarrow 1$ And a bunch of other examples lead me to believe, that I need to do this operation $\lfloor log_{2}{n} \rfloor$ till I get 1.

But how do I go about proving it?

I tried this:

$n=1$ then $\lfloor log_{2}{1} \rfloor$ is $0$ so it's okay.

So let's assume that for $k\lt n$ everythings okay, than we have $T(n)=1+T(\lfloor \frac{n}{2} \rfloor)=\lfloor 1+log_{2}{\lfloor \frac{n}{2} \rfloor} \rfloor=\lfloor log_{2}{2 \lfloor \frac{n}{2} \rfloor \rfloor}$, which doesn't lead me anywhere sensible.

Or do I instead have to prove, that it would take me at most $\lfloor log_{2}{n} \rfloor$ steps? I'm trying to estimate time complexity of an algorithm and I need at least a rough estimation.

-

1 Answer

HINT: Write $n$ in binary (base two). Suppose that the binary representation is $b_kb_{k-1}\ldots b_1b_0$; show that the binary representation of $\left\lfloor\frac{n}2\right\rfloor$ is $b_kb_{k-1}\ldots b_1$, the result of shifting the bit string one place to the right (with consequent loss of the rightmost bit). We may assume that $b_k=1$, so it’s going to take $k$ of these shifts to reduce the number to $1$. But

$$n=\sum_{i=0}^kb_i2^i\;,$$

so $2^k\le n<2^{k+1}$. That’s equivalent to what statement about $\log_2n$?

-
Cool beans, thanks very much :) – Arek Krawczyk Oct 24 '13 at 12:16
@Arek: You’re very welcome. – Brian M. Scott Oct 24 '13 at 12:17