Expected comparisons, from first principles

HardProgramming & DSA~7m

Randomized quicksort sorts $4$ distinct keys by picking a uniformly random pivot, comparing every other key to it, recursing on the two parts. Derive the exact expected number of key comparisons (to four decimal places). Do not quote the $2n\ln n$ asymptotic - compute the exact value for $n=4$ .

Show hints (2)+

Ranks $z_i,z_j$ are compared iff the first pivot drawn from the block $z_i..z_j$ is one of the two endpoints - probability $2/(j-i+1)$ .
Sum $2/(j-i+1)$ over all pairs by rank-distance: $3(1)+2(\tfrac23)+1(\tfrac12)$ .

Answer

Reveal answer →

4.8333 (± 0.001)

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Prop Trading

Expected comparisons, from first principles

Answer

Related questions