Engineering/Mathematics/Algorithm analysis
Asymptotic Notation and Machine Models
A number-theoretic algorithm's cost is measured in bit operations against an input whose size is its bit length, not its value. Getting that convention right is what separates a polynomial-time algorithm from an exponential one that looks linear.
- Analysis foundation
- Complexity
- Cost model discipline
- ≈14 min read
- Applies to every algorithm page
01
Executive summary
Complexity claims in this field are only meaningful relative to two conventions: what counts as one operation, and how input size is measured. For number-theoretic algorithms the answers are bit operations and bit length, and both differ from the defaults assumed in general algorithm courses.
The consequence appears immediately. Trial division to √n looks like a fast algorithm when n is treated as the input size; measured against the length of n, it is exponential. Every security argument in cryptography depends on stating the model correctly.
| Model | Unit of cost | Appropriate when | Risk |
|---|---|---|---|
| Bit complexity | one bit operation | Operands grow with the input — RSA, factoring, big-integer work | Verbose; hides constant-factor engineering |
| Arithmetic complexity | one field or ring operation | The base ring is fixed — finite field algorithms, linear algebra | Misleading if the ring elements grow |
| Word RAM | one machine-word operation | Operands fit in a word; practical implementation analysis | Assumes unit-cost multiplication of O(log n)-bit words |
Always state which model a bound refers to. 'O(n³) for modular exponentiation' is meaningless without saying whether n is the modulus or its bit length.
02
Asymptotic notation
O, Ω, Θ, o, ω
- f = O(g): there are c, x0 with |f(x)| ≤ c·g(x) for x ≥ x0 — an upper bound.
- f = Ω(g): g = O(f) — a lower bound.
- f = Θ(g): both hold — a tight bound.
- f = o(g): f/g → 0 — strictly smaller order.
- f = ω(g): f/g → ∞.
- The equals sign is an abuse of notation. f = O(g) means membership in a set. It is not symmetric, and chains such as O(n) = O(n2) read left to right only.
- Soft-O. Õ(f) means O(f·(log f)k) for some constant k — a convenient way to state results that assume fast multiplication without tracking log factors.
- Uniformity matters. When a bound involves two parameters, say the modulus size and the exponent size, state which one the constant is uniform in; hidden dependence on a second parameter is a common source of incorrect claims.
- Constants are not always negligible. Schönhage–Strassen multiplication is asymptotically superior to Karatsuba but only becomes faster above a few thousand bits. Crossover points are engineering facts that asymptotics deliberately discard.
03
Input size and the polynomial-time boundary
The single most common error in this field
The input size of an integer n is ℓ = ⌊log2 n⌋ + 1 bits, not n. An algorithm running in time O(n) or O(√n) is exponential in the input size, because n = 2ℓ. This is why trial division, the sieve of Eratosthenes and Pollard rho are not polynomial-time factoring algorithms, however fast they are on small inputs.
| Class | Form | Example |
|---|---|---|
| Linear | O(ℓ) | Integer addition and comparison |
| Quadratic | O(ℓ2) | Schoolbook multiplication; Euclid's algorithm |
| Cubic | O(ℓ3) | Modular exponentiation with classical arithmetic |
| Polynomial | ℓO(1) | AKS primality proving |
| Subexponential | Ln[α, c], 0 < α < 1 | Quadratic sieve (α = ½), number field sieve (α = ⅓) |
| Exponential | 2Ω(ℓ) | Trial division; generic discrete log at O(√q) |
L-notation
The parameter α is the one that matters for extrapolating key sizes. Moving from the quadratic sieve to the number field sieve reduced α from ½ to ⅓, which is why RSA modulus sizes had to grow substantially in the 1990s.
04
Machine models
A model must be fixed before any bound is meaningful. Three are in common use, and results transfer between them with known overheads.
Turing machine
Sequential tape access. The reference model for complexity theory, but tape movement inflates costs by polynomial factors that are irrelevant in practice.
RAM with unit-cost operations
Random access, arithmetic on unbounded integers at unit cost. Convenient but dishonest for big-integer work, since it hides the cost of multiplying large numbers.
Word RAM (logarithmic cost)
Random access with O(log n)-bit words and unit-cost word operations. The model that matches real hardware and the one implicitly used in implementation analysis.
Reconciling the models
Number-theoretic results are usually stated in bit complexity, which is model-independent up to constant factors across reasonable machines. Implementation analyses are stated in word operations. The translation is a division by the word size w for linear-time operations, and by w2 for schoolbook multiplication — so a 64-bit machine gains a factor of roughly 4096 on multiplication relative to a bit-serial count.
- Parallelism and memory hierarchy are outside all three models. The linear algebra stage of a factoring record is bounded by memory bandwidth and interconnect latency, not by operation counts; asymptotic analysis says nothing about it.
- Randomised models add a source of random bits and admit Las Vegas algorithms (always correct, random running time) and Monte Carlo algorithms (fixed running time, small error probability). Miller–Rabin is Monte Carlo; ECPP-style primality proving is Las Vegas.
- Quantum models change the picture entirely for this domain: Shor's algorithm factors and computes discrete logarithms in polynomial time, which is why post-quantum schemes rest on different problems altogether.
05
Stating and using cost models correctly
| Question | Why it matters |
|---|---|
| Is the input size the value or its bit length? | Determines whether an algorithm is polynomial or exponential |
| Bit operations, ring operations or word operations? | A factor of ℓ or ℓ2 hangs on the answer |
| Classical or fast arithmetic assumed? | O(ℓ2) versus Õ(ℓ) multiplication changes every downstream bound |
| Worst case, average case or expected over internal randomness? | Miller–Rabin's 1/4 is worst case over inputs, not average |
| Is the bound conditional? | Several results assume the extended Riemann hypothesis |
| Are pre-computation costs included? | Index calculus amortises an expensive setup over many later logarithms |
Worked model statement
A correct statement reads: Modular exponentiation of an ℓ-bit base by an ℓ-bit exponent modulo an ℓ-bit modulus takes O(ℓ3) bit operations using schoolbook multiplication, or Õ(ℓ2) using fast multiplication. Both figures, and the assumption behind each, belong in the statement.
- Report crossover points alongside asymptotics when recommending an implementation; Karatsuba typically wins above roughly 300–600 bits, and FFT-based methods only above several thousand.
- Distinguish amortised from per-operation costs: Montgomery multiplication has a setup cost that pays for itself only across many operations with the same modulus.
- State whether a bound counts modular multiplications or bit operations when comparing exponentiation strategies — sliding-window methods reduce multiplication counts, not the cost of each one.
06
Quick reference and FAQ
| Operation | Bit operations | With fast multiplication |
|---|---|---|
| Addition, subtraction, comparison | O(ℓ) | O(ℓ) |
| Multiplication | O(ℓ2) | Õ(ℓ) |
| Division with remainder | O(ℓ2) | Õ(ℓ) |
| gcd, extended gcd | O(ℓ2) | Õ(ℓ) |
| Modular exponentiation | O(ℓ3) | Õ(ℓ2) |
| Jacobi symbol | O(ℓ2) | Õ(ℓ) |
| Miller–Rabin, k rounds | O(kℓ3) | Õ(kℓ2) |
| Conversion to decimal | O(ℓ2) | Õ(ℓ) |
Why is the sieve of Eratosthenes not a polynomial-time algorithm?
Does the choice of Turing machine versus RAM ever change a conclusion?
Why do papers report Õ bounds so often?
How should security levels be derived from these bounds?
08
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — §3.1–3.2.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 — Chapter 3.
- D. E. Knuth, The Art of Computer Programming, Vol. 2, 3rd ed., Addison-Wesley, 1997 — §4.3 on classical arithmetic costs.
- D. Harvey and J. van der Hoeven, 'Integer multiplication in time O(n log n)', Annals of Mathematics 193 (2021) 563–617.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: asymptotic-notation-and-machine-modelsReview cycle: annual