Selection in expected linear time: Why am I getting $O(n)$ bound instead of $\Omega(n \lg n)$? 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) &amp; \text{if $n \le K$} \\
T(\lceil n/3 \rceil)+T(2n/3+4) + O(n) &amp; \text{if $n \ge K$} 
\end{cases}$$

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

$$\begin{aligned}
T(n) &amp; \le \lceil n/3 \rceil + c(2n/3 + 4) + an \\
     &amp; \le cn/3 + c + 2cn/3 + 4c + an \\
     &amp; = cn + 5c + an \\
     &amp; = (c+a)n + 5c \\
     &amp; = 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?
You started with the induction hypothesis $T(k) \le ck/3$ for all $k&lt;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.