0
$\begingroup$

I have tried to solve this recurrence relation using induction. $$T(n) = T(\lfloor \log_2 n \rfloor) +1$$ It is clear that I should get something similar to $\log *n$, but I don't know how to formalize this kind of questions. Thank you for your kind help.

$\endgroup$
0
$\begingroup$

That $\lfloor \log_2 n \rfloor$ suggests you should plug in powers of $2$ and see if something interesting happens: (Assume $T(1)$ is given) \begin{align} T(2) &= T(\lfloor \log_2 2 \rfloor) +1 \\ &= T(1) +1; \\ T(4) &= T(\lfloor \log_2 4 \rfloor) +1 \\ &= T(2) +1 \\ &= T(1) +2; \\ T(8) &= T(\lfloor \log_2 8 \rfloor) +1 \\ &= T(3) +1 \\ &= T(1) +3; \\ T(16) &= T(\lfloor \log_2 16 \rfloor) +1 \\ &= T(4) +1 \\ &= T(1) +4; \end{align} and so on. Then, you notice that $T(2^m) = T(1) +m$; you may prove it by induction (the inductive step will make use of the recurrence relation.)

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