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?

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

1 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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.