Selection in expected linear time: Why am I getting $O(n)$ bound instead of $\Omega(n \lg n)$? [duplicate]

Question

The problem is from CLRS 9.3-1:

In the algorithm SELECT, the input elements are divided into groups of $5$. Argue that SELECT does not run in linear time if groups of $3$ are used.

If we do the "divide by $3$" technique, we will come up with this recurrence --

$$T(n) = \begin{cases} \Theta(1) & \text{if $n \le K$} \\ T(\lceil n/3 \rceil)+T(2n/3+4) + O(n) & \text{if $n \ge K$} \end{cases}$$

I have solved by substituting $T(n) \le cn$ and $O(n) = an$ --

$$\begin{aligned} T(n) & \le \lceil n/3 \rceil + c(2n/3 + 4) + an \\ & \le cn/3 + c + 2cn/3 + 4c + an \\ & = cn + 5c + an \\ & = (c+a)n + 5c \\ & = c_1n + c_2 \le c_1n \approx O(n) \end{aligned}$$

But the solution says it should be $\Omega(n \lg n)$. I understand that substitution like $cn \lg n$ could give $\Omega(n \lg n)$ bound, but what is wrong with $O(n)$ formulation above?

Answer 1

You started with the induction hypothesis $T(k) \le ck/3$ for all $k<n$, but you didn't prove that $T(n)\le cn$. You concluded that $T(n) \le c_1 n$, for a different constant $c_1 \ne c$. For the induction proof to work, you have to use the same constant in the induction hypothesis and the conclusion.