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!
Although the final result is correct, your solution is not.

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