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:
- The correct answer is $T(n) =O(n log n).$
- 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 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 $kleq 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
