Sorting & hashing formulas

The successful-search average assumes the key is present and equally likely to be at each of the $n$ positions. Both the worst case and the average case are $O(n)$.

Convention: each probe of a[mid] counts as one (three-way) comparison. The worst case $\lfloor {\log }_{2}n\rfloor +1$ holds for both successful and unsuccessful search. If a question counts the == test and the < test as separate comparisons, recount under its rule. Valid only for a sorted array with random access.

Method: take the elements in pairs. Compare the two elements of each pair with each other, then the smaller with the current minimum and the larger with the current maximum. That is 3 comparisons per pair instead of 4. Finding only the maximum (or only the minimum) takes exactly $n-1$ comparisons. Both counts are the best possible for comparison-based algorithms.

Any sort that learns about the keys only by comparing pairs of them must make $\Omega (n\log n)$ comparisons in the worst case, and also on average. Proof idea: there are $n!$ possible orderings of $n$ distinct keys. A binary decision tree that distinguishes them all has at least $n!$ leaves, so its height is at least $\lceil {\log }_2(n!)\rceil$, and ${\log }_2(n!)=\Theta (n\log n)$ by Stirling's approximation.

The maximum occurs for reverse-sorted input. The expected value is for a uniformly random permutation of $n$ distinct keys, since each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs is inverted with probability $\frac{1}{2}$. Insertion sort runs in $\Theta (n+I)$ time, so it is fast on nearly sorted input.

This applies whenever a problem of size $n$ is split into 2 equal halves with linear combine cost. The recursion tree has ${\log }_{2}n$ levels, each costing $\Theta (n)$ in total.

Even a lopsided but constant-fraction split, such as 1 : 9, gives $\Theta (n\log n)$. Only a split that leaves a constant number of elements on one side at every level gives $\Theta (n^2)$.

This is for the standard two-pointer merge of sorted lists of sizes $m$ and $n$. The worst case $m+n-1$ occurs when the lists interleave. The best case $\min (m,n)$ occurs when every element of the shorter list is smaller than every element of the longer one.

Bottom-up build-heap is $O(n)$, not $O(n\log n)$, because most nodes sit near the bottom and sift down only a short distance. Heap sort is build-heap followed by $n-1$ extract-max operations: $O(n)+O(n\log n)=O(n\log n)$.

$n$ = number of elements; the keys are integers in $\mathrm{0..}k-1$. The sort is linear when $k=O(n)$ and degrades when $k$ is much larger than $n$. It is stable when the output is filled by scanning the input from right to left, as below. It is not in-place.

$d$ = number of digits (passes) and $k$ = the range of one digit ($k=10$ for decimal digits, $k=2$ for bits). Least-significant-digit radix sort applies a stable sort, usually counting sort, once per digit. The total is linear when $d$ is a constant and $k=O(n)$. It is not in-place.

$n$ = number of keys stored, $m$ = number of slots. With chaining, $\alpha$ can exceed 1. With open addressing every key needs its own slot, so $\alpha \le 1$. The open-addressing formulas below need $\alpha <1$, i.e. at least one free slot.

These count the keys examined. An unsuccessful search walks the whole chain, whose expected length is $\alpha$. A successful search examines the target plus the keys inserted into the same chain after it. Including the $O(1)$ hash computation, both searches take $\Theta (1+\alpha )$ time. In the worst case, when all $n$ keys hash to one slot, a search takes $\Theta (n)$.

These are upper bounds, valid for $\alpha <1$. Uniform hashing is an idealisation that double hashing approximates well. Linear and quadratic probing do worse because of clustering.

Valid for $\alpha <1$. The squared term in the unsuccessful case shows how quickly primary clustering hurts as the table fills up.