# Big-O Notation

**Type:** Concept  
**Domain:** Discrete Mathematics  
**Codex URL:** /mathematics/discrete/big-o-notation/  
**Entry status:** Live — v1.0 (2026-05-27)

## Summary
Describes algorithm growth rate as input size increases, ignoring constants.

## Definition
f(n)=O(g(n)) if ∃ C,n₀ such that f(n)≤C·g(n) for all n≥n₀.

## Common growth rates
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

## Related notations
Big-O (upper bound), Big-Ω (lower bound), Big-Θ (tight bound).

## Historical origins
Paul Bachmann (1894, number theory) → Edmund Landau (popularized, "Landau notation") → Donald Knuth (1968+, systematized for CS in *The Art of Computer Programming*).

## P vs NP
P = solvable in O(nᵏ) time. NP = verifiable in polynomial time. Whether P=NP is a $1M Clay Millennium Prize Problem, unsolved.

## Amortised analysis
Tarjan (1980s) — bounds average cost per operation across a sequence, even with occasional expensive individual operations.

## Sources
### Tier 1
- Cormen, T.H. et al. (2022). *Introduction to Algorithms*. 4th ed.
- Knuth, D.E. (1976). *ACM SIGACT News*.
### Tier 2
- Sipser, M. (2012). *Introduction to the Theory of Computation*. 3rd ed.

---
*Mathematics Codex entry v1.0 — added 2026-05-27 — thecodex.expert/mathematics/*