Complexity scenarios

The best case is the input that makes the algorithm do the least work: the target is the first element of a linear search (1 comparison), or the array is already sorted for insertion sort (n - 1 comparisons). It is rarely useful for planning because it is unrepresentative.

Run the three cases in the animation to see the comparison counts.

1static int comparisons(int[] arr, int target) {
2    int count = 0;
3    for (int x : arr) {
4        count++;
5        if (x == target) return count;       // best case 1, worst case n
6    }
7    return count;                            // absent: always n
8}
9// average over all n present targets, equally likely: (1 + 2 + ... + n) / n = (n + 1) / 2

The average case is the expected cost over a stated distribution of inputs. If the target is equally likely to be at any of the n positions, a successful linear search makes (n + 1)/2 comparisons on average. An average claim is only meaningful with the distribution attached.

Real inputs often are not uniform, so average-case results should be checked against the actual workload.

1static int comparisons(int[] arr, int target) {
2    int count = 0;
3    for (int x : arr) {
4        count++;
5        if (x == target) return count;       // best case 1, worst case n
6    }
7    return count;                            // absent: always n
8}
9// average over all n present targets, equally likely: (1 + 2 + ... + n) / n = (n + 1) / 2

The worst case is the most expensive input of a given size: the target is last or absent, giving n comparisons. Worst-case bounds are guarantees that hold for every input, which makes them the standard for planning and for real-time systems.

Quick sort is O(n²) in the worst case but O(n log n) on average; heap sort is O(n log n) in all cases.

1static int comparisons(int[] arr, int target) {
2    int count = 0;
3    for (int x : arr) {
4        count++;
5        if (x == target) return count;       // best case 1, worst case n
6    }
7    return count;                            // absent: always n
8}
9// average over all n present targets, equally likely: (1 + 2 + ... + n) / n = (n + 1) / 2

Expected cost averages over the algorithm's own random choices, not over the input. Randomised quick sort picks pivots at random, so for every input its expected number of comparisons is about 2n ln n ≈ 1.39 n log₂ n. No particular input is bad on average.

Average-case analysis assumes a random input; expected-case analysis assumes a random algorithm.

Amortised cost is the average cost per operation over a worst-case sequence of operations. ArrayList.add is O(n) when the array is full and must be copied, yet n adds in a row cost O(n) in total, so each add is amortised O(1) with no assumptions about the input.

The next lesson develops three methods (aggregate, accounting, potential).

1void add(int x) {
2    if (size == data.length) {                          // full: allocate a bigger array
3        data = Arrays.copyOf(data, newCapacity(data.length));   // copies `size` elements
4    }
5    data[size++] = x;                                   // the cheap part: 1 write
6}
7// doubling: newCapacity = 2 * capacity;  grow-by-1: capacity + 1;  Java ArrayList: capacity + capacity / 2

Average results depend on how inputs are distributed. Uniformly random keys make a plain binary search tree about 1.39 log₂ n deep on average, but already-sorted keys make it a chain of depth n. Hash tables assume well-spread hashes; adversarial keys can break that.

When the distribution is unknown or adversarial, prefer worst-case guarantees or randomise.

Bounds for randomised algorithms come in two forms. Expected bounds average over the random choices (randomised quick sort: O(n log n) expected). High-probability bounds say the cost is within a bound with probability at least 1 - 1/nᶜ, which is stronger and survives repeated use.

Las Vegas algorithms always return the correct answer with random running time; Monte Carlo algorithms have bounded time and a small probability of error.