I want to show that the recursion of quicksort run on best time time on n log n.
i got this recursion formula
M(0) = 1
M(1) = 1
M(n) = min (0 <= k <= n-1) {M(K) + M(n - k - 1)} + n
show that M(n) >= 1/2 (n + 1) lg(n + 1)
what i have got so far:
By induction hyposes
M(n) <= min {M(k) + M(n - k - 1} + n
focusing on the inner expresison i got:
1/2(k + 1)lg(k + 1) + 1/2(n - k)lg(n - k)
1/2lg(k + 1)^(k + 1) + 1/2lg(n - k)^(n - k)
1/2(lg(k + 1)^(k + 1) + lg(n - k)^(n - k)
1/2(lg((k + 1)^(k + 1) . (n - k)^(n - k))
But i think im doing something wrong. i think the "k" should be gonne but i cant see how this equation would cancel out all the "k". So, probably, im doing something wrong
You indeed want to get rid of k. To do this, you want to find the lower bound on the minimum of M(k) + M(n - k - 1). In general it can be arbitrarily tricky, but in this case the standard approach works: take derivative by k.
((k+1) ln(k+1) + (n-k) ln(n-k))' =
ln(k+1) + (k+1)/(k+1) - ln(n-k) - (n-k)/(n-k) =
ln((k+1) / (n-k))
We want the derivative to be 0, so
ln((k+1) / (n-k)) = 0 <=>
(k+1) / (n-k) = 1 <=>
k + 1 = n - k <=>
k = (n-1) / 2
You can check that it's indeed a local minimum.
Therefore, the best lower bound on M(k) + M(n - k - 1) (which we can get from the inductive hypothesis) is reached for k=(n-1)/2. Now you can just substitute this value instead of k, and n will be your only remaining variable.