Big-O Notation

If an algorithm takes 3n² + 7n + 42 operations, its Big-O is O(n²). We drop constants (3×) and lower-order terms (7n, 42) because as n grows toward infinity, the n² term dominates everything else. Big-O describes the worst-case growth behavior, not the actual runtime on a specific machine. Two algorithms that are both O(n log n) can differ by 10× in practice — Big-O won't tell you which is faster for small n.

O(1) is constant time — hash table lookups, array access by index. O(log n) algorithms like binary search halve the problem each step. O(n) means you touch each element once. O(n log n) is the theoretical minimum for comparison-based sorting. O(n²) appears in naive nested-loop algorithms and becomes painfully slow above ~10,000 elements. O(2ⁿ) explodes so fast it's only practical for very small inputs (n < 30).

To find Big-O: identify the loop structure. A single loop over n elements is O(n). Two nested loops over n elements is O(n²). A loop that halves its range each iteration (while n > 1: n /= 2) is O(log n). If you call an O(log n) function inside an O(n) loop, the result is O(n log n). When loops are sequential (not nested), you add complexities and keep the dominant term: O(n) + O(n²) = O(n²).

// O(n²) — two nested loops
for (let i = 0; i < n; i++)
  for (let j = 0; j < n; j++)
    process(i, j);

// O(n log n) — loop + binary search
for (let i = 0; i < n; i++)
  binarySearch(arr, target); // O(log n) each

Space complexity applies the same notation to memory usage. An algorithm that creates a copy of the input array uses O(n) extra space. An in-place sort uses O(1) extra space. Recursive algorithms implicitly use O(depth) stack space — a recursive binary search uses O(log n) stack frames, a naive recursive Fibonacci uses O(n) stack frames. When you see "in-place" in a problem, it usually means O(1) extra space required.