Linear Probing: Analysis

If there are no collisions, the performance for insert/remove and search is $O(1)$; this is the best-case scenario.

The worst-case scenario is when probing sequence goes over every occupied position. This is $O(n)$ where $n$ is the number of items stored in the hash table.

Given an open-address hash table with load factor $\alpha$, the expected number of probes in an unsuccessful search (or for inserting an element) is at most $\frac{1}{1 - \alpha}$ assuming uniform hashing.

Proving this claim is beyond the scope of this class. Interested reader is referred to the CLRS: Theorem $11.6$ and Corollary $11.7$.

The take-home message: since $\alpha < 1$ in open-address hash tables, the average (expected) performance is constant time.

Resources