What is the complexity of the follwoing recurrence? $$T(n) = T(n-1) + 1/n$$I highly suspect the answer to be $O(1)$, because your work reduces by $1$ each time, so by the $n$th time it would be $T(n-n) = T(0)$ and your initial task reduces to 0.
What is the complexity of recurrence $T(n) = T(n-1) + 1/n$
time complexity
By unfolding $$T(n) = T(n-1) + \frac{1}{n} = T(n-2) + \frac{1}{n} + \frac{1}{n-1} = \dots=T(0) + \sum_{k=1}^{n} \frac{1}{k}$$Now we can easily approximate the sum on the RHS using that$$\sum_{k=1}^{n}\frac{1}{k} \le 1 + \int_{1}^{n}\frac{1}{x} dx = 1+ \log{n} - \log{1} = 1+ \log{n}$$Therefore $T(n) \equiv O(\log{n})$