Pseudocode :

Quicksort(A; p; r )

if p < r

q = Partition(A; p; r )

Quicksort(A; p; q - 1)

Quicksort(A; q + 1; r )

Partition(A; p; r )

x = A[r ] // x is selected as a pivot element

i = p - 1

for j = p to r - 1

if A[j ] x

i = i + 1

exchange A[i ] with A[j ]

exchange A[i + 1] with A[r ]

return i + 1

Suppose that the partitioning algorithm always produces a 2-to-9 proportional split. That is, the size of one obtained subproblem divided by the size of the other subproblem is 2/9. Write the recurrence on the running time of Quicksort in this case.