Time Complexity

How runtime grows with input

Big O notation describes how an algorithm's runtime grows as the input size n grows. Crucially, it does not measure exact milliseconds — it measures the rate of growth. A O(n) algorithm and a O(n²) algorithm might both finish in 1 ms on 10 elements, but on a million elements the gap is catastrophic.

The common classes, from fastest to slowest

• O(1) — constant. Array index, hash lookup. Runtime does not depend on n.
• O(log n) — logarithmic. Binary search. Each step halves the work.
• O(n) — linear. Single loop over the input.
• O(n log n) — linearithmic. Efficient sorts (merge, quick, heap).
• O(n²) — quadratic. Nested loops over the same input.
• O(2ⁿ) — exponential. Naïve Fibonacci, brute-force subsets. Becomes unusable around n=40.

Reading code to find Big O

The shape of your loops reveals the complexity:

for (int i = 0; i < n; i++) { ... }       // O(n) — one pass

for (int i = 0; i < n; i++)               // O(n²) — nested loops
  for (int j = 0; j < n; j++) { ... }

while (n > 1) n /= 2;                      // O(log n) — halving

for (int i = 0; i < n; i++)               // O(n + m) — sequential, not nested
  ...
for (int j = 0; j < m; j++)               //   → add the terms
  ...

Drop the constants and lower-order terms

Big O is asymptotic — it cares only about the dominant term as n → ∞:

3n + 5       →  O(n)         // drop the constant 3 and the +5
2n² + 100n   →  O(n²)        // n² dominates as n grows
n + log n    →  O(n)         // n dominates log n

Big O tells you which algorithm wins at scale. For small inputs, constants matter more — a O(n²) sort can beat a O(n log n) sort on arrays under ~20 elements. This is why real libraries switch to insertion sort for tiny partitions.

Why nested loops matter

Each nested loop multiplies the work. Two nested loops over n give n × n = n². Three give n³. But a loop followed by another (not nested) gives n + n = O(n) — you add, not multiply. Reading nesting depth is the fastest way to estimate complexity.