Expected Running Time

We can use the notion of expectations to characterize the running time of a randomized algorithm.

The expected running time is $\sum_t t \Pr\{t\}$, where t is a possible running time for the algorithm and $\Pr\{t\}$ is the probability that this running time occurs.