Big O notation
A way of writing an upper bound on growth: O(f(n)) means the cost grows no faster than a constant times f(n) for large n.
In more detail
Big O is the notation engineers use every day, as in "dict lookup is O(1)" or "nested loops are O(n^2)". Formally, cost is O(f(n)) if some constant c and starting size exist beyond which cost never exceeds c times f(n). Because it is only an upper bound, O(n^2) is technically true of a linear algorithm too, which is why big Theta exists for exact rates.
Examples
O(1), O(log n), O(n), O(n log n), O(n^2)React diffing is linear in the number of elements, which is why it stays fast for large trees.Related terms
- big Omega notation — A way of writing a lower bound: Omega(f(n)) means the cost grows at least as fast as a constant times f(n) for large n.
- big Theta notation — A way of writing an exact growth rate: Theta(f(n)) means the cost is both O(f(n)) and Omega(f(n)).
- growth rate — The rule that says how fast an algorithm's cost rises as the input size n rises, such as constant, linear or quadratic.
- asymptotic analysis — Studying how an algorithm's cost behaves as the input size grows very large, ignoring constant factors and small inputs.
- diffing algorithm — The rules React uses to compare an old element tree with a new one and find what changed.
Taught in
- Space, In-Place Work And The Call Stack — Algorithms & Data Structures for Working Engineers
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers
- Diffing Algorithm: Element Type Shifts And Subtree Tear Down — React 19 & Modern Component Architecture