Problem Detail: 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.
Asked By : John Swoon
Answered By : 0xdeadcode
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})$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/35429 Ask a Question Download Related Notes/Documents
