Example

Note that there are cases in which the expected running time of an algorithm is very fast, but there is no bound on the worst-case running time.

$\begin{algorithm} {HaveGirl}{} \begin{REPEAT} \mbox{\it kid} \= \mbox{\sc Rand... ...T}{\mbox{\sc sex}(\mbox{\em kid}) = \mbox{\em female}}\\ \RETURN\end{algorithm}$

$T = 1 + 1/2\; (0) + 1/2\; T$
T = 1 + 1/2 + 1/4 + 1/8 + ...
T = 2

Next: RANDOMIZED QUICKSORT Up: PROBABILITY THEORY Previous: Expected Running Time