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.
$\begingroup$
$\endgroup$
8
-
3$\begingroup$ 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? $\endgroup$– David RicherbyCommented Dec 17, 2014 at 14:36
-
2$\begingroup$ 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 $\endgroup$– babouCommented Dec 17, 2014 at 14:42
-
2$\begingroup$ @babou Yes, this is indeed widespread. Even research papers talk about "complexity of this algorithm". $\endgroup$– RaphaelCommented Dec 17, 2014 at 17:14
-
2$\begingroup$ @babou Everyone thinks "Oh, it's $O(\text{something})$, it must have something to do with time complexity." $\endgroup$– Soham ChowdhuryCommented Dec 17, 2014 at 17:25
-
2$\begingroup$ @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. $\endgroup$– babouCommented Dec 17, 2014 at 17:39
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
3
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})$
-
$\begingroup$ The answer would be better if it criticized the misuse of the word complexity. $\endgroup$– babouCommented Dec 17, 2014 at 14:47
-
3$\begingroup$ 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. $\endgroup$ Commented Dec 17, 2014 at 16:27
-
$\begingroup$ Thanks again @Yuval Filmus. The inequality is correct now. :) $\endgroup$ Commented Dec 17, 2014 at 17:30
$\begingroup$
$\endgroup$
3
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.)
-
1$\begingroup$ Taking into account the asymptotics of the harmonic numbers, the final answer is $T(n) = \log n + O(1)$. $\endgroup$ Commented Dec 17, 2014 at 6:30
-
$\begingroup$ 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. $\endgroup$ Commented Dec 17, 2014 at 9:31
-
1$\begingroup$ 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. $\endgroup$– babouCommented Dec 17, 2014 at 14:56