Big O Notation: The Developer's Practical Guide

Big O describes how an algorithm's time or space requirements grow as input size grows. In interviews, you're expected to state complexity for every solution you write.

The common complexities

How to analyse code

Rule 1: Drop constants

// O(2n) → O(n)
for (int x : arr) { process(x); }  // n
for (int x : arr) { log(x); }       // n

Rule 2: Drop non-dominant terms

// O(n² + n) → O(n²)
for (int i : arr)              // n
  for (int j : arr) { ... }    // n²

Rule 3: Different inputs = different variables

// O(a + b), NOT O(n)
void foo(int[] a, int[] b) {
    for (int x : a) { ... }  // a
    for (int x : b) { ... }  // b
}

Rule 4: Recursion = check the recurrence

Fibonacci naive: each call branches into two → O(2ⁿ) Fibonacci memoized: each value computed once → O(n)

Space complexity

Space complexity measures additional memory used, not the input itself.

• Iterative array algorithm with a hash map: O(n) space
• Recursive DFS on a tree of height h: O(h) stack space
• In-place sorting: O(1) space

Interview tip

State complexity proactively: "This is O(n log n) time and O(1) space." Then the interviewer knows you know — they don't have to ask.