0
$\begingroup$

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(\lfloor n/2 \rfloor)$, $T(0) = 0$, and $2^{r-1} \le n < 2^r$ , $r \ge 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(\lfloor n/2 \rfloor)$ 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.

$\endgroup$
  • $\begingroup$ Your equation looks like $T(n) = 1 + T(\lfloor \square / 2 \rfloor )$, and there are $\square$ scattered over the rest of the equation. Please don't use obscure unicode, most people's computer's fonts don't support them. The $\square$ appears to be cursive n, is that supposed to be different than the regular n? $\endgroup$ – DanielV Aug 17 '16 at 6:41
1
$\begingroup$

A recurrence relation needs to start with some non-recursive "seed value(s)" in order to be properly defined. This is your $T(0) = 0$. (If you don't have these, then your definition is self-referetial.)

You then apply the relation using the initial value:

$$T(1) = 1 + T(\lfloor 1/2 \rfloor) = 1 + T(0) = 1 + 0 = 1$$ $$T(2) = 1 + T(\lfloor 2/2 \rfloor) = 1 + T(1) = 1 + 1 = 2$$ $$T(3) = 1 + T(\lfloor 3/2 \rfloor) = 1 + T(1) = 1 + 1 = 2$$ $$T(4) = 1 + T(\lfloor 4/2 \rfloor) = 1 + T(2) = 1 + 2 = 3$$

From above, you can see that the condition holds for a few base cases. Now you apply induction. Assume $T(n) = r$ holds for $2^{r-1} \le n < 2^r$ and prove it holds for an $m$ where $2^r \le m < 2^{r+1}$.

Your calculation will look something like this: $$T(m) = 1 + T(\lfloor m/2 \rfloor) = 1 + T(2^r / 2) = 1 + T(2^{r-1}) = 1 + T(n) = 1 + r$$

where you'll need to justify some of those equalities.

| cite | improve this answer | |
$\endgroup$

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.