Experiment bears this out.
This could be improved by writting a recursion formula for the expected running time for n=k in terms of the expected running times for n=0, 1, ..., k-1.
To me the recursion looks something like (but don't expect this to be exactly right, it needs checking):
t(k)=1+(2/k)[t(0)+t(1)+.. + t(k-1)]
where t(k) is the expected running time when n=k.