Runtime that is analyzed over all possible random choices.