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

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?

• See our reference question for proper techniques to use here. Also, this issue is specifically addressed in CLRS. – Raphael Jul 22 '13 at 14:01
• @Raphael That's my bad, I did not pay heed to that chapter well. Thanks for the links and the suggestions. – Khaled Jul 30 '13 at 18:53

## 1 Answer

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.