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 n/3 - 1 values in the 'less than' bucket and 2n/3 in the 'greater than' bucket.  
We recursively select from that 'greater than' bucket, so "T(2n/3)" for that step.



That makes the recurrence for "n" end up as T(n) = n + T(2n/3)