RandomizedQuickSort

Randomized quicksort is a popular divide-and-conquer sorting algorithm. Below is the pseudo-code for this algorithm:

function quicksort(A)
	if (length(A) <= some constant S) then
		return slowsort(A)
	else
		k = random integer drawn uniformly from integers in [0, length(A) - 1]
		(left, pivot, right) = partition(A, k)

		return concatenate(quicksort(left), pivot, quicksort(right))
	end if
end function


function partition(A, k)
	pivot = A[k]

	// We are assuming that the list contains no duplicates, so no other element is equal to the pivot
	left = elements in A that are smaller than pivot
	right = elements in A that are larger than pivot
	return (left, pivot, right)
end function

Assume that partition(A) takes a * length(A) time units and slowsort(A) takes b * length(A)^2 time units. Further assume that the total running time is simply equal to the sum of the running times of all calls to partition() and slowsort(). As seen in the pseudo-code, quicksort does not call itself recursively on lists of length S or less, but instead calls slowsort().

Consider using the randomized quicksort algorithm to sort a list that is some permutation of elements {x | 1 <= x <= listSize}. Hence, the list is of length listSize, only contains integers between 1 and listSize, inclusive, and contains no duplicates. You are given the constants a, b and S, and asked to compute the expected total running time of randomized quicksort on a list of size listSize that obeys the constraints given above.