Worst-Case, Average-Case, and Best-Case Analysis

Three Kinds of Analysis

For an input size $n$ , define the cost function $C(x)$ for a specific input instance $x$ :

Worst-case: $W(n) = \max_{x: |x|=n} C(x)$ — the maximum cost over all inputs of size $n$ .
Best-case: $B(n) = \min_{x: |x|=n} C(x)$ — the minimum cost over all inputs of size $n$ .
Average-case: $A(n) = \mathbb{E}[C(x)]$ — the expected cost, assuming some probability distribution over inputs.

Insertion Sort as Canonical Example

Recall the cost expression for Insertion Sort:

$T(n) = an + (b+c+g)(n-1) + d\sum_{j=2}^{n} t_j + (e+f)\sum_{j=2}^{n} (t_j - 1)$

where $t_j$ is the number of WHILE-loop iterations for iteration $j$ . The value of $t_j$ depends on how far $A[j]$ must travel into the sorted prefix.

Best Case ( $\Theta(n)$ )

Input is already sorted. Every $t_j = 1$ (only the failing comparison at loop entry). The sums collapse to linear terms, giving $T(n) = \text{linear function} = \Theta(n)$ .

Worst Case ( $\Theta(n^2)$ )

Input is reverse-sorted. Each $j$ requires moving $j-1$ elements (plus the final failing comparison, so $t_j = j$ ):

$\sum_{j=2}^{n} t_j = \sum_{j=2}^{n} j = \frac{n(n+1)}{2} - 1$

$\sum_{j=2}^{n} (t_j - 1) = \sum_{j=2}^{n} (j-1) = \frac{n(n-1)}{2}$

Both sums are $\Theta(n^2)$ , so $T(n) = \Theta(n^2)$ .

Average Case ( $\Theta(n^2)$ )

Assume all permutations of the input are equally likely. On average, half the elements in $A[1 \dots j-1]$ are smaller than $A[j]$ and half are larger, so the inner loop runs $j/2$ times. This yields the same arithmetic progression with a factor of $1/2$ , still $\Theta(n^2)$ . The average case is often the same order of magnitude as the worst case.

Why Worst-Case Matters

Guarantees: An $O(n^2)$ worst-case bound means the algorithm will never exceed that asymptotic cost for any input. This is essential for real-time and safety-critical systems.
Adversarial inputs: Worst cases may occur in practice. A human sorting a list is unlikely to provide reverse-sorted input, but programmatic data sources might.
Average case often equals worst case: For many algorithms (including Insertion Sort), the average and worst cases are the same asymptotic order, so there is no reason to use a weaker analysis.

Analysis vs Benchmarking

Asymptotic Analysis	Benchmarking
Predicts behaviour for all input sizes	Measures behaviour on specific inputs
Machine-independent (RAM model)	Machine-dependent (CPU, cache, OS)
Ignores constants	Captures real constants
Good for algorithm comparison	Good for implementation tuning

The RAM model analysis is useful for algorithmic decisions (MergeSort over Insertion Sort for large $n$ ). Benchmarks become useful for small $n$ , where constants dominate.

Summary

Case	Insertion Sort	Definition
Best	$\Theta(n)$	Already-sorted input
Worst	$\Theta(n^2)$	Reverse-sorted input
Average	$\Theta(n^2)$	Random permutation, each element moves ~ $i/2$ positions
Why worst	Provides guarantees, often similar to average