What is Big-O notation?

Big-O notation describes how an algorithm’s running time (or memory) grows as the input size grows, focusing on the dominant term and ignoring constants. It expresses the worst-case upper bound, which lets you compare algorithms independent of hardware.

Common complexities from fastest to slowest: O(1) constant (a hash lookup), O(log n) logarithmic (binary search), O(n) linear (a single loop), O(n log n) (efficient sorts like merge sort), O(n²) quadratic (nested loops over the same input), and O(2^n) or O(n!) (brute-force combinatorial problems).

In interviews you use Big-O to justify your approach: state the time and space complexity of your solution, compare it to the brute force, and explain the trade-off. For example, sorting first (O(n log n)) can turn an O(n²) pairwise comparison into O(n log n). The skill being tested is reasoning about scalability, not memorising a table.