Engineering / Mathematics — Orientation
Useful Facts and Standard Estimates
The analytic inequalities, series estimates and elementary bounds relied on repeatedly in the analysis of number-theoretic algorithms.
Executive summary
Algorithm analysis in this field leans on a small, recurring set of analytic facts: bounds on harmonic sums, estimates for binomial coefficients, the behaviour of the exponential and logarithm near critical points.
These are collected here so that the analysis pages can cite them rather than reproving them.
Learning objectives
- Recall the standard inequalities used in complexity proofs.
- Apply harmonic and logarithmic estimates to running-time analysis.
01Exponential and logarithmic bounds
Fundamental exponential inequality
For all real x, 1 + x ≤ e^x, with equality only at x = 0.
Consequently (1 − 1/k)^k < 1/e for k ≥ 1.
This single inequality carries an unreasonable share of the analysis in this subject. It is the reason repeating a randomised test k times drives the failure probability below any fixed threshold, and the reason the birthday bound takes the shape it does.
For 0 ≤ x ≤ 1: 1 − x ≤ e^(−x) ≤ 1 − x + x²/202Harmonic sums
Harmonic sum estimate
The sum H_n = 1 + 1/2 + ... + 1/n satisfies ln n < H_n < 1 + ln n, and H_n = ln n + γ + O(1/n) where γ is the Euler–Mascheroni constant.
Harmonic sums appear whenever a loop runs over divisors or over primes below a bound. The sieve of Eratosthenes and trial division bounds both reduce to estimating sums of this shape.
03Binomial and factorial estimates
- Factorial, crude
n! ≤ n^nSufficient for most upper bounds - Factorial, Stirling
n! ~ √(2πn)(n/e)^nNeeded when the constant matters - Central binomial
4^n/(2n+1) ≤ C(2n,n) ≤ 4^nUsed in Chebyshev-type prime bounds - General binomial
C(n,k) ≤ (en/k)^kConvenient in counting arguments
04Counting and probability bounds
Two elementary bounds recur in the probabilistic analysis.
- The union bound: the probability of any of a collection of events is at most the sum of their probabilities. Crude, but almost always sufficient and never wrong.
- The pigeonhole principle in its counting form: if n objects occupy k classes then some class holds at least
⌈n/k⌉objects.
Sharper concentration results — Markov's and Chebyshev's inequalities — are developed properly in the probability stream rather than listed here.
05Frequently asked questions
Why is 1 + x ≤ e^x so ubiquitous?
Because failure probabilities multiply. If a single trial fails with probability at most 1 − p, then k independent trials all fail with probability at most (1 − p)^k, and the inequality converts that product into e^(−pk), which is far easier to reason about and to invert for k.
When is Stirling's approximation actually needed?
Rarely for upper bounds, where n! ≤ n^n suffices. It becomes necessary when a proof needs the growth rate of a binomial coefficient to within a polynomial factor, as in the sharper prime-counting estimates.
Is the union bound too weak to be useful?
It is weak, and it is still the right first tool. It requires no independence assumption, which is precisely the situation in most algorithm analyses. Sharper bounds are reached for only when the union bound fails to give the needed result.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 501-503.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.