Recurrence relation $T(n) = T(n-1)+\frac 1n$

Question

How can we solve this recurrence relation $T(n) = T(n-1)+\frac 1n$

I would like to calculate the time complexity of the algorithm.

Answer 1

You can "solve" the recurrence relation to get (assuming $T(1) = 1$) something like

$$ T(n) = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$$

This is the harmonic series, which is famously very close to $\log_e(n)$.

Answer 2

\begin{align}T(n) &=T(n-1) +\frac{1}{n}\\ &=T(n-2) +\frac{1}{n-1} +\frac{1}{n}\\ &=T(n-3) +\frac{1}{n-2} +\frac{1}{n-1} +\frac{1}{n}\\ &\vdots\\ &=T(1) +\sum_{k=2}^n \frac{1}{k}. \end{align}