# Solution verification: solving $T(n) = T(n-1) + 2/n$

I was wondering if someone could possibly verify my solution to the following:

I'm trying to solve the recurrence relation $T(n) = T(n-1) + 2/n$. To get it into the form of the Master Theorem, I note that for sufficiently large $n$, $n - 1 \geq n/2$. Moreover, $2/n = O(1)$. Thus, we can rewrite the equation as $T(n) = T(n/2) + O(1)$. Since $\log_21 = 0$, it then follows directly from the Master Theorem that $T(n) = O(\log(n))$.

-Thanks!

• 1) $n-1 \geq n/2$ implies that you derived a lower bound ($\Omega$). 2) "check my answer" questions are bad for this platform. 3) See our reference question.
– Raphael
Feb 4 '15 at 8:05
• Master theorem does not apply in your case Oct 17 '18 at 20:30

The recurrences of the form $T(n) = T(n-1) + 2/n$ is often called "decrease and conquer"; while the ones of the form $T(n) = T(n/2) + O(1)$ is called "divide and conquer". Generally, they are different and cannot be reduced to each other.
Hint: To solve $T(n) = T(n-1) + 2/n$, you can expand it and notice that $1 + 1/2 + \cdots + 1/n = H(n) = \Theta(\lg n)$, the $n$-th partial sum of the harmonic series (wiki).
No, this solution is unfortunately false. You remark that for sufficiently large $n$, $n-1 \geq n/2$ (indeed, $n \geq 2$ would do). The recurrence easily implies that $T$ is increasing, so $n-1 \geq n/2$ implies that $T(n-1) \geq T(n/2)$. All you can deduce is that $T(n) \geq T(n/2) + 2/n$, which cannot imply any upper bound on $T(n)$. Even the lower bound you get is only $\Omega(1)$.
If you forget about the Master Theorem, then you can notice that \begin{align*} T(n) &= T(n-1) + \frac{2}{n} \\ &= T(n-2) + \frac{2}{n-1} + \frac{2}{n} \\ &= \cdots \\ &= T(0) + \frac{2}{1} + \cdots + \frac{2}{n} \\ &= T(0) + 2H_n, \end{align*} where $H_n = \sum_{k=1}^n (1/k)$ is the $n$th Harmonic number. It is well-known that $H_n = \log n + \Theta(1)$ (indeed, the complete asymptotic series is known), and so $T(n) = 2\log n + \Theta(1)$.