1
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – PKG
    Commented Oct 7, 2016 at 19:45
  • 2
    $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Commented Oct 7, 2016 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.