Engineering / Mathematics — Integer Algorithms
Asymptotic Notation for Algorithm Analysis
Big-O, Omega, Theta and little-o notation, the conventions that make them precise, and the pitfalls of using them carelessly.
Executive summary
Asymptotic notation describes how a cost function grows, discarding constants and lower-order terms. In this field it is not a convenience but a necessity: the algorithms operate on numbers whose size is the input, and exact operation counts are both unobtainable and uninformative.
The notation is routinely abused. Treating O as an equality, comparing bounds rather than costs, and ignoring the variable of growth all produce confident false conclusions.
Learning objectives
- Define the four asymptotic relations precisely.
- Identify the variable of growth in a multi-parameter bound.
- Avoid the standard misuses of the notation.
01The four relations
Asymptotic relations
For functions f, g positive for large arguments:
f = O(g) if f(n) ≤ c · g(n) for some constant c and all large n.
f = Ω(g) if g = O(f). f = Θ(g) if both hold.
f = o(g) if f(n)/g(n) → 0.
The equals sign is a historical accident and reads badly: O(g) denotes a class of functions and the relation is membership, not equality. It is never symmetric, so O(n) = O(n²) is true read left to right and false read right to left.
- Logarithmic
O(log n)Binary search; length of a number - Linear
O(n)Single pass over the digits - Quadratic
O(n²)Schoolbook multiplication of n-bit numbers - Subexponential
L(1/3)Number field sieve; between polynomial and exponential - Exponential
O(2^n)Brute-force search over n-bit keys
02Input size is bit length, not value
This is why the field distinguishes carefully between algorithms polynomial in the value and polynomial in the length. Only the latter are efficient. An algorithm running in time O(n) on an input of value n is useless for cryptographic sizes, where n has 2048 bits.
| Algorithm | In terms of value n | In terms of length ℓ | Efficient? |
|---|---|---|---|
| Trial division | O(√n) | O(2^{ℓ/2}) | No |
| Euclid's algorithm | O(log² n) | O(ℓ²) | Yes |
| Miller–Rabin | O(log³ n) | O(ℓ³) | Yes |
| Number field sieve | subexponential | L(1/3) | Not polynomial, but feasible |
03Multi-parameter bounds and hidden variables
Bounds in this field frequently involve two quantities — the modulus length and an exponent length, or a degree and a field size. Stating which is growing is part of the bound, not an afterthought.
Soft-O notation Õ(f) suppresses logarithmic factors and is common when those factors are genuinely secondary. It should be used only when the reader can be trusted to know what has been hidden.
04Frequently asked questions
Is O(n) always better than O(n²)?
As a bound, yes; as a running time, not necessarily. Bounds are upper limits and may be loose. An algorithm proved O(n²) may in practice run faster than one proved O(n) with a large constant, and asymptotic superiority only guarantees an advantage beyond some crossover point that may lie past all practical input sizes.
Why does subexponential get its own category?
Because factoring and discrete logarithm algorithms land there, and the distinction matters for parameter selection. L(1/3) grows faster than any polynomial but far slower than 2^ℓ, which is precisely why RSA moduli must be thousands of bits rather than hundreds.
Should constants ever be tracked?
Yes, whenever two algorithms share an asymptotic class. Karatsuba and schoolbook multiplication differ asymptotically, so the constant decides only the crossover; but two O(ℓ²) implementations differ only in the constant, and that is the entire comparison.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 33-36.
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.