1
$\begingroup$

In the book of "Introduction to Algorithm 3rd Edition", p.86, there is subtitled, "Avoiding pitfalls", and it states

When

$T(n) = 2 \cdot T(\lfloor(n/2)\rfloor)+n$

, and if we want to prove $T(n)=O(n)$ by guessing $T(n) \leq cn $ and the argument of this

$T(n) \leq 2(c\lfloor(n/2)\rfloor) +n$

$\leq cn + n$

$=O(n)$ <== Wrong!

since $c$ is a constant.

I don't understand why above is wrong? Could someone explain above, please?

$\endgroup$
8
  • 2
    $\begingroup$ If you assume $T(n)\leq cn$, then obviously $T(n)=O(n)$, since you've assumed what you want to prove. The rest of the argument isn't needed, but the whole procedure is fallacious. $\endgroup$
    – saulspatz
    Nov 24, 2020 at 22:59
  • $\begingroup$ @saulspatz This seems to be meant to be inductive proof, i.e. It is assumed to be valid for "smaller" $n$ and we are proving it is valid for "this" $n$. $\endgroup$
    – user700480
    Nov 24, 2020 at 23:03
  • 1
    $\begingroup$ @breadncup If you assume $T(k)\le ck$ for $k\lt n$, you are meant to prove $T(n)\le cn$ and not $T(n)\le (c+1)n$. The intuition why this is wrong is that your "constant" $c$ is not really a constant as it seems to have "crept up" (by $1$) in the inductive step. $\endgroup$
    – user700480
    Nov 24, 2020 at 23:07
  • 1
    $\begingroup$ The above is wrong because each time you’re applying the induction hypothesis the “constant” $c$ grows. $\endgroup$
    – Aphelli
    Nov 24, 2020 at 23:07
  • $\begingroup$ @StinkingBishop Perhaps you're right. The argument seems like it starts in the middle to me. $\endgroup$
    – saulspatz
    Nov 24, 2020 at 23:08

1 Answer 1

0
$\begingroup$

Firstly let me note, that for $n=2^k$ and $T(n) = 2 \cdot T(\lfloor(n/2)\rfloor)+n$ we can obtain $T(n)=nT(1)+n \log_2 n$, so it is not $O(n)$.

About mistake in proof: 86p. clearly says reason as authors see it

  • "The error is that we have not proved the exact form of the inductive hypothesis, that is, that $T(n) \leqslant cn$. We therefore will explicitly prove that $T(n) \leqslant cn$ when we want to show that $T(n) =O(n)$."

But, as we know, mathematical induction $$\forall P\Big(P(0) \land \forall k(P(k) \Rightarrow P(k+1)) \Rightarrow \forall n(P(n))\Big)$$

does not require explicit prove of inductive hypothesis $P(k)$, but the implication $\forall k(P(k) \Rightarrow P(k+1))$.

So to prove exact form of induction firstly we need clearly set what is $P$.

  1. If we assume, that $P(n)$ is "$T(n) =O(n)$", then we come to question how to understand initial step of induction, which, in this case, becomes $T(1) =O(1)$. As we know in formal definition of "$T(n) =O(n)$", the "$n$" is the variable in definition under universal quantifier, it is so called bound variable. Exact formulation of sentence $f(x) \in O(g(x))$, $x \to x_0$ means, that we need two functions $f,g$ from variable $x$ and limit point $x_0$. So we can consider, that $P(n)$ is "$T \in O(n)$" and under "$n$" we understand identity function $I(n)=n$. So formally we come to "$T \in O(I)$".

  2. If we assume, that $P(n)$ is "$T(n) \leqslant cn$", this will fix $c$. So initial step of induction, in this case, is $T(1)\leqslant c $. Now we need to prove $P(k) \Rightarrow P(k+1)$, which is $T(k) \leqslant ck \Rightarrow T(k+1) \leqslant c(k+1)$. But using suggested in book proof we obtain only $T(k+1) \leqslant c(k+1)+(k+1)$, which, sure, is not what we wanted.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .