Selection in expected linear time: Why am I getting $O(n)$ bound instead of $\Omega(n \lg n)$?
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.