Big-O (time complexity)

Applies to: general

Big-O describes how an algorithm's cost grows with input size n, ignoring constants: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n^2) quadratic. It is how you reason about whether code will scale.

lookup in a hash map      -> O(1)
binary search             -> O(log n)
scan a list               -> O(n)
compare all pairs         -> O(n^2)

See also: loop, hash-map, recursion