Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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$?

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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