How to solve a recurrence when the master theorem fails?
You can explicitly unroll the recursion:
$$
\begin{align*}
T(n) &amp;= \frac{1}{n} + \frac{1}{2} T\left(\frac{n}{2}\right) \\ &amp;=
\frac{1}{n} + \frac{1}{n} + \frac{1}{4} T\left(\frac{n}{4}\right) \\ &amp;= \cdots \\ &amp;=
\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.