# Big O Notation
## Algorithms — The Codex Coding
**URL:** https://thecodex.expert/coding/algorithms/complexity/
**Type:** algorithm | **Confidence:** high | **Last verified:** 2026-06-01

## CANONICAL DEFINITION
Big O notation describes the asymptotic upper bound on the growth rate of an algorithm's time or space requirements as a function of input size n, abstracting away constant factors and lower-order terms to characterise how the algorithm scales.

## COMPLEXITY
- O(1): constant
- O(log n): logarithmic
- O(n): linear
- O(n log n): linearithmic
- O(n^2): quadratic
- O(2^n): exponential

## REQUIRES
concepts/loops, concepts/recursion

## ENABLES
algorithms/sorting, data-structures

## COMMONLY CONFUSED WITH
O(1) means constant not fast; O(n log n) is not O(n^2); average vs. worst case are different

## SOURCES
- CLRS 4th ed. Ch.3
- Knuth 1976 ACM SIGACT News 8(2)
- Bachmann 1894 Die analytische Zahlentheorie
- Sedgewick & Wayne Algorithms 4th ed.

*The Codex Coding — thecodex.expert/coding/ — Free forever — Mumbai, India*