0
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Feb 4 '15 at 8:05
  • $\begingroup$ Master theorem does not apply in your case $\endgroup$
    – HackerBoss
    Oct 17 '18 at 20:30
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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