1
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by David Richerby, jonaprieto, R B, Juho, Raphael Dec 17 '14 at 17:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\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 Richerby Dec 17 '14 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$ – babou Dec 17 '14 at 14:42
  • 2
    $\begingroup$ @babou Yes, this is indeed widespread. Even research papers talk about "complexity of this algorithm". $\endgroup$ – Raphael Dec 17 '14 at 17:14
  • 1
    $\begingroup$ @babou Everyone thinks "Oh, it's $O(\text{something})$, it must have something to do with time complexity." $\endgroup$ – Soham Chowdhury Dec 17 '14 at 17:25
  • 1
    $\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$ – babou Dec 17 '14 at 17:39
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The answer would be better if it criticized the misuse of the word complexity. $\endgroup$ – babou Dec 17 '14 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$ – Yuval Filmus Dec 17 '14 at 16:27
  • $\begingroup$ Thanks again @Yuval Filmus. The inequality is correct now. :) $\endgroup$ – 0xdeadcode Dec 17 '14 at 17:30
1
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ Taking into account the asymptotics of the harmonic numbers, the final answer is $T(n) = \log n + O(1)$. $\endgroup$ – Yuval Filmus Dec 17 '14 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$ – Soham Chowdhury Dec 17 '14 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$ – babou Dec 17 '14 at 14:56

Not the answer you're looking for? Browse other questions tagged or ask your own question.