7
$\begingroup$

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.
$\endgroup$
  • 4
    $\begingroup$ No you can't. Your induction hypothesis is $T(n)\le cn$, and this is what you have to prove. Actually, the recurrence does not solve to $O(n)$. $\endgroup$ – A.Schulz Jul 31 '12 at 18:24
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks , I understood the point and ofcourse it is meaningless to have new constant for every $n$. But how you had written " or equivalently ...."(third statment) i.e. can we always find such $c$ for which $n_0$ is $1$. $\endgroup$ – Saurabh Jul 31 '12 at 20:50
  • 2
    $\begingroup$ In practice, $c = 10^{10^{100!}}$ usually works. $\endgroup$ – JeffE Jul 31 '12 at 20:56
  • $\begingroup$ @SaurabhHota: Given $n_0$ and $c$ from the first form, $c + \max_{n \leq n_0} T(n)/n$ works as constant for the second form. The other direction is immediate, i.e. the constant carries over with $n_0=1$ (or an arbitrary value, in fact). $\endgroup$ – Raphael Aug 1 '12 at 7:07

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.