2
$\begingroup$

This question already has an answer here:

How do solve the following recurrence?

$$ T(n) = \frac{1}{2} T\left(\frac{n}{2}\right) + \frac{1}{n}. $$

Master's theorem cannot be applied as $a$ is equal to 0.5 which is less than 1. Hence the theorem fails. How do I solve a recurrence when the theorem fails?

$\endgroup$

marked as duplicate by adrianN, David Richerby, Evil, Rick Decker, Juho Feb 7 '17 at 16:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

You can explicitly unroll the recursion: $$ \begin{align*} T(n) &= \frac{1}{n} + \frac{1}{2} T\left(\frac{n}{2}\right) \\ &= \frac{1}{n} + \frac{1}{n} + \frac{1}{4} T\left(\frac{n}{4}\right) \\ &= \cdots \\ &= \frac{m}{n} + \frac{1}{2^m} T \left(\frac{n}{2^m}\right). \end{align*} $$ This easily leads to the solution $$T(n) = \frac{\log_2 n + T(1)}{n},$$ which is valid for powers of 2.

$\endgroup$

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