Originally Posted by

**Constatine11** Roughly speaking we should expect the average running time to be roughtly linear in n (as at each recursion we replace a computation of f(n) by two computations of something like f(n/2)).

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.