7.4-2

Show that quicksort’s best-case running time is $\Omega(n lg n)$.
for best case we need to have at least element to left side of the tree.(see CLRS about the ratio q and 1-q)
$$T(n) = min_{1 \leq q \leq n-1} (T(q)+T(n-q-1))+\theta(n)$$ lets use substitution method. lets assume $T(n) \geq c n lg n $ $$T(n) = min_{1 \leq q \leq n-1} (c q log q+ c (n-q-1) log(n-q-1))+\theta(n)$$ to find maximum and minimum we need to use calculus. Refer
http://www.youtube.com/watch?v=tBBJ2TSTa1Q
http://www.1728.org/minmax.htm
If the second derivative is positive q ln q+ (n-q-1) ln(n-q-1)/ln we get a minimum value:
$$f(n) = q ln q+ (n-q-1) ln(n-q-1)/ln 2$$ $$f'(n) = ln q+ 1- ln(n-q-1)-1/ln 2$$ $$f'(n) = ln q - ln(n-q-1)/ln 2$$ slope is zero at minimum
ln q - ln(n-q-1) = 0
q = n-1/2
Now we need to see if the second derivative is positive $$f''(n) = 1/q + 1/(n-q-1)/ln 2$$ lets substitute q = (n-1)/2 $$f''(n) = 2/(n-1) + 1/(n-((n-1)/2)-1)/ln 2$$ $$f''(n) = (4/n-1)/ln 2$$ if $n \geq 2$ then above equation is always postive hence the minimum value occurs when q = (n-1)/2 substituting q value in eq at the top. $$T(n) = (c (n-1)/2 log (n-1/2)+ c (n-(n-1/2)-1) log(n-(n-1/2)-1))+\theta(n)$$ $$T(n) = (c (n-1)/2 log (n-1/2)+ c (n-1)/2 log((n-1)/2)+\theta(n)$$ $$T(n) = (c (n-1) log (n-1/2)+ \theta(n)$$ $$T(n) = (c (n-1) log (n-1)- c(n-1)+ \theta(n)$$ $$T(n) = (c n log (n-1) - c log (n-1)- c(n-1)+ \theta(n)$$ $$T(n) = (c n log (n-1) - c log (n-1)- c(n-1)+ \theta(n)$$ $$T(n) \geq (c n log (n/2) - c log (n-1)- c(n-1)+ \theta(n)$$ since $n \geq 2$ $$T(n) \geq (c n log (n) -cn - c log (n-1)- c(n-1)+ \theta(n)$$ $$T(n) \geq (c n log (n) - c (n - log (n-1)- (n-1))+ \theta(n)$$ if we pick a small value for c so $\theta(n)$ is larger than n - log (n-1)- (n-1) then $$T(n) = \Omega(n log n)$$