Big-O & Complexity

How to measure an algorithm before you run it: time and space complexity, common growth rates, and how to read constraints in an interview.

Why complexity matters

Two programs can give the same answer and still be wildly different: one finishes in a millisecond, the other runs for an hour. Big-O notation describes how the work grows as the input size n grows, ignoring constant factors and small terms. It is the language every coding interview uses.

Rule of thumb: about 10⁸ simple operations per second. If n = 10⁵, an O(n²) solution does 10¹⁰ operations, which is far too slow. O(n log n) does about 1.7 million, which is instant.

The common growth rates

Reading constraints like a pro

Interviewers hint at the expected complexity through the input size:

• n ≤ 10 → O(n!) or O(2ⁿ) backtracking is fine
• n ≤ 20 → O(2ⁿ) bitmask or backtracking
• n ≤ 500 → O(n³) DP
• n ≤ 5000 → O(n²)
• n ≤ 10⁵ – 10⁶ → O(n log n) or O(n)
• n ≥ 10⁹ → O(log n) or O(1) (math or binary search on the answer)

How to compute Big-O

1. Loops multiply: a loop inside a loop over n is O(n²).
2. Sequential steps add, and you keep the biggest: O(n) + O(n log n) = O(n log n).
3. Halving the problem each step gives O(log n).
4. Recursion: count the nodes of the recursion tree × the work per node. Two branches with depth n gives O(2ⁿ).
5. Space counts extra memory: arrays, hash maps, and the recursion stack (depth h means O(h) space).

Code template

# O(1): constant
def first(a): return a[0]

# O(n): one pass
def total(a):
    s = 0
    for x in a: s += x
    return s

# O(n^2): all pairs
def count_pairs(a, k):
    return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] + a[j] == k)

# O(log n): halve the range every step
def halvings(n):
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

// O(1): constant
int first(int[] a) { return a[0]; }

// O(n): one pass
long total(int[] a) { long s = 0; for (int x : a) s += x; return s; }

// O(n^2): all pairs
int countPairs(int[] a, int k) {
    int c = 0;
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++) if (a[i] + a[j] == k) c++;
    return c;
}

// O(log n): halve the range every step
int halvings(int n) { int steps = 0; while (n > 1) { n /= 2; steps++; } return steps; }

// O(1): constant
int first(const vector<int>& a) { return a[0]; }

// O(n): one pass
long long total(const vector<int>& a) { long long s = 0; for (int x : a) s += x; return s; }

// O(n^2): all pairs
int countPairs(const vector<int>& a, int k) {
    int c = 0;
    for (size_t i = 0; i < a.size(); i++)
        for (size_t j = i + 1; j < a.size(); j++) if (a[i] + a[j] == k) c++;
    return c;
}

// O(log n): halve the range every step
int halvings(int n) { int steps = 0; while (n > 1) { n /= 2; steps++; } return steps; }

// O(1): constant
const first = a => a[0];

// O(n): one pass
const total = a => { let s = 0; for (const x of a) s += x; return s; };

// O(n^2): all pairs
function countPairs(a, k) {
  let c = 0;
  for (let i = 0; i < a.length; i++)
    for (let j = i + 1; j < a.length; j++) if (a[i] + a[j] === k) c++;
  return c;
}

// O(log n): halve the range every step
function halvings(n) { let steps = 0; while (n > 1) { n = Math.floor(n / 2); steps++; } return steps; }

Amortised complexity

Appending to a dynamic array (Python list, Java ArrayList, C++ vector) is occasionally O(n), when it has to grow. Over many appends the total is still O(n), so each append is amortised O(1). The same argument explains why a monotonic stack or a sliding window is O(n): every element is pushed and popped at most once.

Common mistakes

• Forgetting that s[i:j] slicing or string concatenation in a loop copies data (O(k) each time).
• Calling list.index, x in list or list.pop(0) inside a loop: each is O(n). Use a set, a dict or a deque.
• Ignoring recursion-stack space in DFS (O(h), which can be O(n) for a skewed tree).