# Cannot see why this formula is wrong

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?

• 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. Nov 24, 2020 at 22:59
• @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$.
– user700480
Nov 24, 2020 at 23:03
• @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.
– user700480
Nov 24, 2020 at 23:07
• The above is wrong because each time you’re applying the induction hypothesis the “constant” $c$ grows. Nov 24, 2020 at 23:07
• @StinkingBishop Perhaps you're right. The argument seems like it starts in the middle to me. Nov 24, 2020 at 23:08

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.