[Solved]: Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$

Problem Detail: 

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$.
The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing

$\qquad \begin{align*} T(n) & \leq 2(c \lfloor n/2 \rfloor ) + n \\ &\leq cn +n \\ &=O(n) \quad \quad \quad \longleftarrow \text{ wrong!!} \end{align*}$

since $c$ is constant.The error is that we have not proved the exact form of the inductive hypothesis.

Above I have exactly quoted what the book says. Now my question is why cannot we write $cn+n=dn$ where $d=c+1$ and now we have $T(n) \leq dn$ and hence $T(n) = O(n)$?

Note:

1. The correct answer is $T(n) =O(n \log n).$
2. The book I am referring here is Introduction to algorithms by Cormen et al., page 86, 3rd edition.

Asked By : Saurabh

Answered By : Raphael

The authors give the answer:

The error is that we have not proved the exact form of the inductive hypothesis, that is, that $T(n) \leq cn$.

Granted, that is hard to understand if you are not used to do inductions (right), because they do not do the induction explicitly/rigorously. In short: you need to have one constant $c$ for all $n$, but this (un)proof constructs many (one per $n$).

---

In long, remember what $T(n) \in O(n)$ means:

$\qquad \displaystyle \exists c \in \mathbb{N}.\, \exists n_0 \in \mathbb{N}.\, \forall n \geq n_0.\, T(n) \leq cn$

or, equivalently,

$\qquad \displaystyle \exists c \in \mathbb{N}.\, \forall n \in \mathbb{N} T(n) \leq cn$.

The second form works better for an induction as you know the anchor. So you need one constant $c$ that provides an upper bound for all $n$.

Let's inspect what the induction does:

• Induction anchor: The anchor of $T$ is not explicitly given, but it's constant, so we find a suitable $c$.
• Induction hypothesis: There is some $c$ so that $T(k) \leq cn$ for all $k\leq n$, for some arbitrary but fixed $n$.
• Inductive step: as shown in the question, construct $d > c$ so that $T(n+1) \leq dn$.

So, in effect, we construct a new constant for every $n$. That does not fit the definition of $O$ at all! And, worse, it is completely meaningless: every function can be "bounded" by any other function if you can adjust the factor with $n$.

Regarding the induction proof, $c$ has to be part of the claim (and it is, hidden in the $O$), that is bound "outside" of the induction. Then, the same $c$ shows up in anchor, hypothesis and step. See the last part of this answer for an example.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2971