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.

  • $\begingroup$ Yeah the problem must be stated incorrectly. $T(n) = 1 + T(\lfloor n/2\rfloor)$ must hold only for $n \geq 1$. $\endgroup$ – Ashvin Swaminathan Jul 25 '16 at 1:38
  • $\begingroup$ The question is not well phrased, they should have put $T(0)=0$ first, or last, but not in between. The recurrence, they say explicitly, holds when $2^{r-1}\le n$, $r\ge 1$, so it does not hold at $n=0$. $\endgroup$ – André Nicolas Jul 25 '16 at 1:38
  • $\begingroup$ T (0)=0 is the definition. $\endgroup$ – fleablood Jul 25 '16 at 1:42
  • $\begingroup$ Right, T (0)=0 is the definition. Thanks for pointing that out, I don't know what I was thinking. $\endgroup$ – thePetester Jul 25 '16 at 9:06

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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – thePetester Jul 25 '16 at 9:55
  • $\begingroup$ 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. $\endgroup$ – Jorge Fernández Hidalgo Jul 25 '16 at 14:46

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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