# Cormen Edition 3 Exercise 7.4 Question 3 (Page No. 184)

59 views
Show that the expression $q^2 +(n-q-1)^2$ achieves a maximum over $q=0,1,\dots ,n-1$ when $q=0$ or $q=n-1$.

this might help.

## Related questions

1
182 views
Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.
Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst a $\alpha$-to-$(1-\alpha)$ split, as a function of $\alpha$ in the range $0<\alpha<1$.
We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is nearly sorted. Upon calling quicksort on a subarray with fewer than $k$ elements, let it simply return without sorting the subarray. After the top-level ... runs in $O(nk+n\ lg\ (n/k))$ expected time. How should we pick $k$, both in theory and in practice?