Consider performing Quicksort on an array with n elements, where each element has either

value a or value b$.$ Assume without loss of generality that a $<$ b$.$ Assume there are na

elements with value a and nb elements with value b; so n $=$ na $+$ nb$.$ Assuming the pivot has

value a$,$ explain what the subarrays look like after the Partition step and use this to write

out a recurrence for the left subarray and a recurrence for the right subarray. Solve the two

$1$

recurrences to obtain the running time of Quicksort for this case.

$($Optional: Analyze the subarray$($s$),$ recurrence$($s$)$ and running time when the pivot has value

b$.$