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