Hmm? Expected running time is a valid and important concept. In Quicksort, for example, picking the pivot element randomly results in O(n^2) runtime in the worst case, but has an expected runtime of O(n log(n)). The O(n log(n)) limit can be enforced using the median-of-medians method for pivot selection, but that's a pain to program and has a much higher constant factor than generating a random number; the only benefit being theoretical computer scientists sleep well at night.
Comments
Hmm? Expected running time is a valid and important concept. In Quicksort, for example, picking the pivot element randomly results in O(n^2) runtime in the worst case, but has an expected runtime of O(n log(n)). The O(n log(n)) limit can be enforced using the median-of-medians method for pivot selection, but that's a pain to program and has a much higher constant factor than generating a random number; the only benefit being theoretical computer scientists sleep well at night.