Shoot for an
O
(
n
) expected running time.