at the moment I'm reading "Gems of Theoretical Computer Science" from Schöning and Pruim. In Chapter 8 the book defines a "universal probability distribution" in a way that the Average-Case running-time of every algorithm A under this distribution is equal (up to a constant factor) to it's worst-case running time.
I was wondering why this construction is even helpful. Or in other words I want to know if someone knows a case where this theorem might come in handy.
I know we don't do maths because we want to use it, but because it is beautiful. But I think to talk about this theory as a "gem" of Theoretical Computer Science there should be some serious outcomes of the theory.
In my opinion the best application for this theory would be if there are certain algorithms for which it is very easy to determine the Average-Case running-time but very hard to find out the worst-case running time. But I don't know such a case. I even think that one has to know the worst-case running-time in order to calculate the average-case (that's because the average-running-time is nothing but the expected value of the running time). For example it is easy to show that Quicksort runs in wc O(n^2) but it is harder to show that it runs in ac O(nlog(n)). So it seems pointless to get the average running-time under a certain distribution to be O(n^2). We already knew that.
It would be really nice if someone knew some applications of this theory!