# Nonuniform input distributions in average case analysis

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".

• My definitions for favourable and adversarial case input distributions are different from what you mention. Think of a distribution (not the point distribution) for quicksort, that causes it to perform at $O(n^2)$. E.g. a distribution that leads the array to be already sorted with high probability. – PKG Oct 7 '16 at 19:45
• @PKG, you don't need a special name for that concept: just say that this is a distribution that causes its expected running time to be $\Theta(n^2)$. The great thing about language is that we can express all sorts of new concepts by combining existing words. – D.W. Oct 7 '16 at 19:47