The expected running time of the best possible deterministic algorithm over the worst possible probability distribution on the inputs.