It's also not obvious what "average case" means. For example, if we're talking about the asymptotic behavior of the function A(n) = avg { RunningTime(Algo,

It's also not obvious what "average case" means. For example, if we're talking about the asymptotic behavior of the function A(n) = avg { RunningTime(Algo, x) : x is valid input to Algo and len(x) = n } are we assuming that the inputs are drawn uniformly and therefore have equal weight or are we drawing them from a non-uniform distribution? What if some inputs never occur in practice? Worst case and best case are totally unambiguous and don't need any additional clarification. There are just so many knobs one can adjust when defining "average".