World's most popular travel blog for travel bloggers.

# Nonuniform input distributions in average case analysis

, ,
Problem Detail:

When we perform average case analysis of algorithms, we assume that the inputs to the algorithm are sampled uniformly from some underlying space. For example, the average case analysis of quicksort assumes that the unsorted array is uniformly sampled from the \$n!\$ permutations of \$\{1,\ldots,n\}\$.

Suppose instead that the inputs to an algorithm are chosen non-uniformly over the input space.

Is the resulting analysis still "average case" analysis?

If the distribution causes the algorithm to perform at its worst (resp. best), is there a standard name for it? E.g. "adversarial (resp. favourable) distribution of inputs".

Yes, the expected running time under some other distribution would still count as an example of average-case analysis. However, when you describe it to someone, make sure you explain what distribution you're using. I wouldn't recommend that you just call it "average-case analysis" without also explaining that you're using a non-standard probability distribution.

The worst-case distribution is always a point distribution that assigns all its probability to a single input. In other words, the worst-case probability distribution that makes the expected running time as large as possible is in fact just a single input: the input that makes the algorithm run as long as possible. Consequently, this kind of worst-case analysis coincides with the "standard" notion of worst-case running time. For this reason, there is no need for a special "name" for this; worst-case running time already covers it.

The same is true for best-case running time and the probability distribution that makes the expected running time as small as possible.