<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>It would be really nice if someone knew some applications of this theory!</p>

CC BY-SA 3.0
2017-05-22T22:56:47.047Z
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.
Joshua Grochow
CC BY-SA 3.0
2017-05-22T22:58:22.437Z
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.
Joshua Grochow
CC BY-SA 4.0
2022-07-24T23:24:37.440Z
This universal distribution is actually very useful and realistic in many contexts. So the takeaway is that you can get the average case analysis wrt this distribution by merely doing a worst case analysis.
Andrew
<kolmogorov-complexity><average-case-complexity><worst-case>
Worst-Case and Average-Case running-time equal with universal p-distribution with kolmogorov-complexity any applications of this theory?
Senf
# Worst-Case and Average-Case running-time equal with universal p-distribution with kolmogorov-complexity any applications of this theory?

(Asked by: username_0 on 2017-05-22)

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!

**Tags:** kolmogorov-complexity, average-case-complexity, worst-case

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_2**: This universal distribution is actually very useful and realistic in many contexts. So the takeaway is that you can get the average case analysis wrt this distribution by merely doing a worst case analysis.  

---

## 0 answers

