What is the complexity of recurrence $T(n) = T(n-1) + 1/n$ [duplicate]

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.

• Problems have complexity, algorithms have running times, (mathematical) functions have growth rates. Are you asking about the growth rate of the mathematical function $T(n)$ or the difficulty of computing it? Dec 17 '14 at 14:36
• I have no idea how these things are being taught today. However I am rather surprised by this apparent misuse or abuse of the word "complexity", and by the fact that no one is reacting to it. From what I understand, this can only reinforce the complete conceptual mishmash that seems to encumber the brains of too many students. As far as I can tell, this has nothing to do with complexity, and the study of asymptotic limits and of Landau notation (Big O and its brothers and sisters) is not the study of complexity, but only a tool for it, and for other purposes. (simultaneous @DavidRiche Dec 17 '14 at 14:42
• @babou Yes, this is indeed widespread. Even research papers talk about "complexity of this algorithm".
– Raphael
Dec 17 '14 at 17:14
• @babou Everyone thinks "Oh, it's $O(\text{something})$, it must have something to do with time complexity." Dec 17 '14 at 17:25
• @Raphael You are right. However it bothers me a bit less as the concepts are very close, complexity being about the cost of algorithms that solve the problem. But asymptotic analysis is just a piece of math that has lots of other uses. Still, being precise and using the right words is essential when doing science. Dec 17 '14 at 17:39

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})$

• The answer would be better if it criticized the misuse of the word complexity. Dec 17 '14 at 14:47
• The inequality is now wrong. In fact, $\sum_{k=1}^n \frac{1}{k} = \log n + \gamma + O\left(\frac{1}{n}\right)$, where $\gamma \approx 0.577 > 0$ is the Euler–Mascheroni constant. Dec 17 '14 at 16:27
• Thanks again @Yuval Filmus. The inequality is correct now. :) Dec 17 '14 at 17:30

Edit

This answer assumed that the OP was looking for the time-complexity of an algorithm that would evaluate the recurrence, so it's probably wrong.

Whatever you do, you have to iterate $n$ times, whatever the base case/starting value. So as $n$ grows without bound, the number of operations also grows linearly with $n$ - implying that the recurrence is $O(n)$.

Look at it this way: To calculate $T(n)$, you need $T(n-1)$, which in turn depends on $T(n-2)$, and so on all way till $T(0)$ (or whatever the lowest allowed value of $n$ is).

Each time, you calculate $\frac{1}{k}$ and add it to the next lower value of $T(k)$, doing $O(1)$ work each time, $n$ times - which adds up to $O(n)$ complexity.

In fact, you can easily represent $T(n)$ in general as

$$T(n) = T(0) + \sum^n_{k=1}{\frac{1}{k}}$$

(which, if you're curious, is equal to $T(0) +H_n$, where $H_n$ is the $n$th harmonic number.)

• Taking into account the asymptotics of the harmonic numbers, the final answer is $T(n) = \log n + O(1)$. Dec 17 '14 at 6:30
• When writing my answer I assumed that OP was looking for the complexity of an algorithm that would calculate the answer, so . . . you're correct. Dec 17 '14 at 9:31
• I guess you computed the cost of a given algorithm, rather than the complexity of the problem it solves. But it is as good an interpretation of the misuse of the word complexity as any other. Dec 17 '14 at 14:56