Algorithms / Expected Runtime
Least You Need to Know: Expected Runtime, Random Choices, and Average Analysis
Expected runtime analysis asks for the average running time under a specified source of randomness, often the algorithm's own random choices. This is central for randomized algorithms such as quickselect and quicksort, where worst-case behavior is possible but rare under random pivots.
The least you need to know
- Expected runtime is an average over a declared probability model.
- Worst-case and expected runtime answer different questions.
- Randomized algorithms often have strong expected performance even if some runs are bad.
- A process with success probability `p` per independent trial has expected waiting time `1/p`.
- To use expected analysis correctly, you must state where the randomness comes from.
Key notation
E[T]
expected running time
randomized algorithm
algorithm whose own choices use randomness
worst case
largest runtime over all inputs or outcomes in scope
Tiny worked example
- Randomized quickselect chooses pivots randomly.
- Some pivot sequences are bad, but many are good.
- Expected analysis averages over all pivot choices.
- The result is expected linear time even though unlucky runs can be slower.
Common mistakes
- Students often mix 'expected over random pivots' with 'average over all possible inputs' without saying which model they mean.
- Expected time is not a guarantee that every run is fast.
- A theorem about expected performance can still coexist with a bad worst-case bound.
How to recognize this kind of problem
- The prompt says randomized, average running time, or expected number of trials.
- The source of randomness is explicit or should be made explicit.
- One bad run does not refute a good expected-time bound.