\begin{align} T(0) & = 0 \\ T(n) & = T(n-1) + \dfrac{1}{n} \end{align} solve the recurrence relation
My work so far:
\begin{align} T(1) & = 1 \\ T(2) & = 1 + \dfrac{1}{2} \\ T(3) & = 1 + \dfrac{1}{2} + \dfrac{1}{3} \\ &\vdots \end{align}
this is the harmonic series, which diverges.
What is the solution to the recurrence relation?
The harmonic series diverges when you take the sum to infinity, but this is just the sum to n, which can be calculated. What I'm basically saying is that I think the harmonic series is the right approach.