Assuming we don't "charge" for picking a random value, "0" for that step.

We still have to partition, so say "n" for that step.

We then have roughly n/4 values in the 'less than' bucket and 3n/4 in the 'greater than' bucket.  
We recursively sort BOTH buckets, so "T(n/4) + T(3n/4)" for that step.



That makes the recurrence for "n" to solve T(n) = n + T(n/4) + T(3n/4)