Quadratic Probing Insertions Are $ε^{-(1+o(1))}$

• Linear probing’s clustering raises expected insertion time to Θ(ε^-2) when only an ε fraction of slots is empty.Source: §1 · p. 1
• Quadratic probing replaces consecutive offsets with square offsets to retain data locality while escaping linear probing’s clustering behavior.Source: §1 · p. 1
• Even an O(1) expected-time bound for a table that is 50% full had remained open before this work.Source: §1 · p. 2
• The analysis considers insertion-only workloads and does not consider deletions.Source: §1 · p. 2
• Theorem 1.1 establishes ε^{-(1+o(1))} expected time for the ((1−ε)n+1)-th insertion when n is prime and 1>ε>1/√log n.Source: §1 · p. 2
• Quadratic probing avoids linear-probing-style clustering up to a subpolynomial factor in ε^-1.Source: §1 · pp. 1–2
• The analysis exploits small intersections between translated prefixes of quadratic probing sequences, a property unavailable to general fixed-offset schemes.Source: §1 · p. 2
• The proof models previous insertions through translation invariance and positive association of free-slot indicators.Source: §1 · p. 2

• A quadratic probing table stores keys in n slots and supports insertions and membership queries.Source: §2 · p. 4
• For a key x, the algorithm examines h(x), h(x)+1^2, h(x)+2^2, … modulo n and stores x in the first empty slot.Source: §2 · p. 4
• For prime n, the first n/2 quadratic-probing offsets are guaranteed to be distinct modulo n.Source: §2 · p. 4
• Positive association means that coordinatewise nondecreasing functions of the variables have nonnegative covariance.Source: §2 · p. 4
• Independent variables and monotone functions of common independent inputs are positively associated.Source: §2 · p. 4
• Every insertion terminates within 2n probes when the table is not full, with later unprobed offsets examined in a fixed order if necessary.Source: §2 · p. 4
• Occupied-set monotonicity preserves set inclusion after applying the same future insertions to two tables.Source: §2 · p. 5

• The Poissonized model inserts N∼Poisson((1−ε)n) keys instead of exactly (1−ε)n keys.Source: §3 · pp. 5–6
• The Poissonized model treats insertions after the table becomes full as no-ops with insertion time 2n.Source: §3 · p. 5
• Poissonization reduces analysis of the fixed-load insertion time to analysis of the Poissonized model.Source: §3 · p. 5
• In the Poissonized table, each free-slot indicator has expectation at least ε and the indicators are positively associated.Source: §3 · p. 6
• The positive-association conclusion depends on Poissonization and need not hold for a fixed number of inserted keys.Source: §3 · p. 6
• Rotational symmetry makes the free-slot vector translation-invariant, so covariance between slots depends only on their offset.Source: §3 · pp. 6–7
• Positive association is established by layering independent Poisson counts, applying Harris’s inequality and occupied-set monotonicity, then taking the layer limit.Source: §3 · pp. 6–7
• All vacancy covariances C(r) are nonnegative, enabling bounds on covariance sums along quadratic-probing offsets.Source: §3 · p. 7

Covariance measure

• R(k) is the largest multiplicity of any difference b^2−a^2 modulo n among distinct probe indices a<b<k.Equivalently, it is the largest coefficient when the covariance sum is expressed using C(0),…,C(k−1).Source: §4 · p. 7

Covariance bound

• The sum of covariances over all distinct pairs among the first k quadratic probes is at most R(k), for prime n and 1≤k≤n/2.This is the central technical proposition linking probe-distance multiplicities to vacancy covariances.Source: §4 · p. 7

Quadratic-distance structure

• For k≤√n, R(k)=k^o(1), so quadratic probe distances are mostly distinct modulo n.This small multiplicity distinguishes quadratic probing from linear probing in the final analysis.Source: §4 · p. 7

Poissonized analysis

• Poissonization makes the covariance terms C(r) nonnegative, allowing any subset sum of them to remain at most 1.The argument uses the variance bound Var(Z)≤n for the number of empty slots.Source: §4 · p. 8

Tail-bound setup

• The covariance estimate is converted into a tail bound relating insertion time T to R(k) in the Poissonized table.The insertion probes 0^2,1^2,…,(k−1)^2 after normalizing the new key’s hash to 0.Source: §5 · p. 8

Positive association

• Positive association enables a bound on the probability that all vacancy indicators among the first k probes are zero.The indicators are treated as positively associated Bernoulli variables, and the analysis controls their joint zero event.Source: §5 · pp. 8–9

Why the stronger inequality matters

• Without positive association, Chebyshev’s inequality yields only Pr[S=0]≤O(ε/k), which is too weak for any nontrivial insertion-time bound in ε^-1.Here the summed variances satisfy ∑_{i=1}^k Var(F_i^2)=Θ(kε).Source: §5 · p. 9

Proof strategy

• The comparison replaces positively associated indicators with independent Bernoulli variables having the same marginals, then applies a Chernoff bound.A convex-function comparison controls the cost of replacing the dependent sum by the independent one.Source: §5 · p. 9

Combining estimates

• The resulting tail estimate combines the positive-association inequality with Proposition 4.1’s covariance bound and eliminates the exponential term by polynomial domination.The exponential term is bounded using e^-x/8=O(x^-2) for x>0.Source: §5 · pp. 8, 10

Translating bounds to insertion time

• The covariance bounds are converted into fixed-load insertion-time tails through Proposition 5.1 and the Poissonization comparison.The resulting cases cover the principal ranges of k, with monotonicity filling gaps between selected values.Source: §6 · pp. 10–11

Covering the extreme regime

• Quadratic probing avoids linear probing’s clustering because its probe differences spread sufficiently that R(k) initially grows at rate k^o(1), rather than Θ(k).The final large-k regime instead conditions on any occupied set and bounds the number of hashes causing very long insertions.Source: §6 · p. 11, §6.2 · pp. 12, 14

Bounding R(k)

• R(k) measures the largest number of pairs among the first k probe indices sharing a square difference modulo n.It is also the largest coefficient in the relevant covariance linear combination.Source: §6.1 · p. 11
• For k ≤ n^1/2, factoring b^2 − a^2 into (b − a)(b + a) reduces the count to a divisor bound.The congruence becomes an integer equality in this range.Source: §6.1 · p. 11

Final expected-time bound

• Theorem 1.1 gives expected insertion time ε^{-(1+o(1))} for prime table size n and 1 > ε > 1/√log n.The insertion considered is the ((1 − ε)n + 1)-th insertion.Source: §7 · p. 14
• The proof may restrict to ε ≤ 1/2 because expected insertion time is nonincreasing in ε, while the ε = 1/2 case supplies the constant bound for larger ε.This reduction is used before the range-by-range summation.Source: §7 · p. 14
• The expectation is bounded by summing Pr[T > k] over probe counts, using that insertion time is at most 2n and the tail is nonincreasing.The proof handles the sum range by range.Source: §7 · p. 14
• Only one probe-count range contributes more than O(ε^-1) to the expectation.The remaining ranges are controlled by the tail bounds established earlier.Source: §7 · pp. 14–15