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

Taught in

References