Some algorithms need access to random numbers, and often different random choices made by the algorithm

can lead to different runtimes. In such a scenario, speaking about the algorithm$$s runtime doesn$$t make

sense as different executions of the same algorithm can have different runtimes. To fix this issue, we speak

instead about the expected running time, which is defined as follows for a randomized algorithm