Lower-order term constraints and wrong guess

Question

I'm a self-taught and I'm studying from CLRS. I'm having difficulty with this recurrence relation: $$T(n)=3T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + n$$

The problem is that I can "prove" that $T(n) = \mathcal{O}(n)$. It's absurd. My inductive hypothesis about $\mathcal{O}(n)$ is: $$\exists c \gt 0 \,\,\exists n_0 \gt 0 \,\,\exists b \ge 0 \quad\forall n_0\le k\lt n \quad T(k) \le ck - bn \le ck $$

From here I haven't problem during the "proof": $$\begin{align} T(n) &\le 3\left(c\left\lfloor{\frac{n}{2}}\right\rfloor - bn\right) + n \\ &\le 3\left(c\frac{n}{2} - bn\right) + n \\ &= \frac{3}{2}cn - 3bn + n \\ &= \frac{3}{2}cn -n(3b - 1) \qquad\qquad (1st) \\ &\le cn \end{align}$$

The latter holds $\forall b \ge \frac{c+2}{6}$ and it comes from: $$\frac{3}{2}cn - n(3b - 1) \le cn$$

--EDIT--
It's also easy to prove that $$(1st) \le cn - bn$$ It holds $\forall b \ge \frac{c+2}{4}$
So $$T(n) \le cn - bn$$ --END EDIT--

So I think that the hypotheses are wrong. Probably I misunderstanding subtraction of lower-order term. What are the constraints to apply this technique? Only that $T(k) \gt 0$? In this recurrence the latter seems valid.

Synthesis: https://cs.stackexchange.com/questions/65549/lower-order-term-constraints-and-wrong-guess/65579?noredirect=1#comment139380_65579

Answer 1

First of all, the way you state the induction hypothesis is a bit strange, and it definitely doesn't prove that $T(n) = O(n)$. Assuming that the induction is on $n$, what your induction hypothesis states (more or less) is that for every $n$ there exists $C$ such that $T(k) \leq Ck$ for all $k \leq n$. The function $T(n) = n^2$ satisfies this, with $C = n$.

What you really want to do is to fix the parameters $b,c,n_0$ in advance. In other words, you want to prove $$ \exists b,c,n_0 \, \forall n \, \forall n_0 \leq k \leq n\colon T(k) \leq ck - bn. $$ You first instantiate $b,c,n_0$, and then you prove only the following part by induction: $$ \forall n \, \forall n_0 \leq k \leq n\colon T(k) \leq ck - bn. $$ At each step of the induction, you are proving $$ \forall n_0 \leq k \leq n\colon T(k) \leq ck - bn $$ for the current value of $n$.

Now for your mistake. Your induction hypothesis states that for all $k \leq n$, $$ T(k) \leq ck - bn. $$ However, in the inductive step, you only prove $$ T(k) \leq ck. $$ Also, you only prove it for $k = n$, despite the form of your actual induction hypothesis.

Indeed, it is very strange that your inductive hypothesis gives an upper bound on $T(k)$ which depends on $n$. This is quite unorthodox. Usually the upper bound only depends on $k$. Moreover, you are not really subtracting a lower-order term: $n \neq o(k)$!

Here is what an application of subtracting a lower-order term usually looks like. Suppose that we want to prove that $T(n) = O(n)$. Then you find $b,c,n_0$ and prove the following by induction:

$$ \forall n \geq n_0\colon T(n) \leq bn - c\log n.$$

Note that there is no $k$ here, and that $\log n = o(n)$ is indeed of lower order.