# How to solve a recurrence when the master theorem fails? [duplicate]

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?

## marked as duplicate by adrianN, David Richerby, Evil, Rick Decker, JuhoFeb 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 Answer

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.