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!

  • 1
    $\begingroup$ I can't think of any off the top of my head, but let me offer this: Rather than a starting point for other investigations, this result may be more of an end point. It uses Kolmogorov complexity to answer the question: is there a distribution D such that for all algorithms their D-average case behavior is equal to their worst case behavior? While I can't think of applications immediately for this particular result, I believe the universal distribution itself has been used to good effect for several results. $\endgroup$ – Joshua Grochow May 22 '17 at 22:56
  • $\begingroup$ In principle you don't need to know worst-case to get average-case. Maybe an upper bound on the worst-case, but if it occurs relatively rarely, then even a very loose upper bound can suffice. $\endgroup$ – Joshua Grochow May 22 '17 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.