1

Just so no one thinks I am trying to get one over on anyone, this is a homework question. I have solved all the other problems, but I don't know where to begin with this one. I am not asking for an answer, just a direction or hint (that I can understand).

Prove by induction that if $T(n) = 1 + T(⌊/2⌋), T(0) = 0$, and $2^{r-1} \leq < 2^ , r ≥ 1$ then $T(n) = r$ (Hint: use induction on r.)

How does T(0) = 0? If I plug n=0 in, would the function not return 1? The floor of T(0/2) is still going to be 0, so calling T(⌊/2⌋) would return 1 still, no? I am clearly missing something.

Additionally, the hint says to use induction on r, but how does that help me with T(n)?

Thanks for any insight provided.

Asinomás
  • 105,651
thePetester
  • 21

1 Answers1

1

We must prove the following statement for every positive integer $r$:

if $2^{r-1}\leq n\leq 2^r$ then $f(n)=r$.

It is clearly true when $r=1$ since Only $1$ satisfies $2^0\leq n< 2^1$ and $T(1)=T(0)+1=1$.

So suppose it is true for $r$, we must prove it is true for $r+1$.

So take $2^{r}\leq n< 2^{r+1}$. Then $2^{r-1}\leq \lfloor n/2 \rfloor < 2^r$.

By the inductive hypothesis $T(\lfloor n/2 \rfloor)=r$ and so $T(n)=r+1$ as desired.

Asinomás
  • 105,651
  • Thanks! I am not sure why I can blow through most of these questions and then something like this just stops me dead in my tracks. – thePetester Jul 25 '16 at 09:55
  • probably just lack of practice, it can be hard to rigorously justify statements when you haven't seen how to do it for similar problems. – Asinomás Jul 25 '16 at 14:46