There are a good reasons why we don't usually do average-case analysis of algorithms, chief among them that we have no idea how inputs are distributed (another reason is computational difficulty). Worst-case bounds are pessimistic, but they hold.
In CS you're often dealing with adversarial inputs, for which worst-case analysis is obviously the right approach. Not sure that there's anything comparable to that in most statistical settings.
frequentist :: Bayesian ~ worst-case analysis :: average-case analysis
There are a good reasons why we don't usually do average-case analysis of algorithms, chief among them that we have no idea how inputs are distributed (another reason is computational difficulty). Worst-case bounds are pessimistic, but they hold.