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

ignougroup
Problem Detail: 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?

Asked By : ramgorur

Answered By : JeffE

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13381