Big-O Notation

Big-O notation describes how the running time or memory use of an algorithm grows as the input size (n) grows, focusing on the worst case and ignoring constant factors. It is used to compare algorithms independently of hardware.

Common complexities, from fastest to slowest growth: O(1) constant, O(log n) logarithmic (binary search), O(n) linear (scanning a list), O(n log n) (efficient sorting), O(n²) quadratic (nested loops) and O(2ⁿ) exponential (naive recursive solutions).