You can compute recursively as below:
We use f(n) to represent the number of comparisons which the
Quick-Sort algo needs to take running on an array of n elements.
Answer to question 1:
f(n) = 2 * f(n/2) + n
We can observe the following sequence of equations:
f(n) = 4 * f(n/4) + 2 * n/2 + n = 4f(
The median of a set of n values is the \lceil n/2 \rceilth smallest
value.
1. Suppose quicksort always pivoted on the median of the current
sub-array. How many comparisons would Quicksort make then in the worst
case?
2. Suppose quicksort were always to pivot on the "n/3 th" smallest
value of
