Consider when quicksort chooses a random pivot. If the pivot chosen comes from the middle 50% of the list, then it is a good pivot, ie: the good pivot is closer to the median than either maximum or minimum.

Since half of the list contains good pivots, we should expect roughly half of the quicksort calls to choose a good pivot.

Suppose we guarantee that every second call, quicksort picks a good pivot. What would be the worst case complexity and recursion depth of quicksorting a list of n unique elements? [2 marks]

Explain your recursion depth using the (smallest) reduction in problem size at each layer, and thus your complexity using the work done at each layer. No explanation no marks. [3 marks]