Big-O / Complexity Analysis

Why this matters / recognition signals

Every other note in this roadmap ends with a complexity claim — “O(n) time, O(1) space” — and an interviewer will probe how you got there, not just whether the final answer matches a memorized table. This isn’t a single algorithm; it’s the analysis skill that sits underneath all of them: reading code shape to derive time/space complexity, solving recurrences for recursive code, and understanding amortized cost so you don’t panic the first time someone points out that a dynamic array occasionally does O(n) work on an “O(1)” append.

Reach for this explicitly when:

You’re asked “what’s the time complexity of this?” for code you didn’t write — read the loop/recursion shape, don’t guess from the problem description.
A solution has nested loops, and you need to know whether they multiply or whether one is bounded by a small constant (making it effectively O(n), not O(n·k)).
A solution is recursive — you need the recurrence relation, not just “it feels like it branches a lot.”
Someone claims an operation is O(1) “on average” or “amortized” and you need to justify why, not just accept it.

Deriving complexity from code shape

Three shapes cover most interview code:

Nested loops multiply. An inner loop that runs m times for each of n outer iterations does n × m total work.

for (int i = 0; i < n; i++) {        // n iterations
    for (int j = 0; j < m; j++) {    // m iterations each
        // O(1) work
    }
}
// total: O(n * m)  — O(n^2) if m == n

Sequential loops add, and the sum is dominated by (i.e. simplifies to) the max. Two separate loops back to back, not nested, cost O(n) + O(m), which Big-O notation reports as O(n + m) — or just O(n) if m ≤ n and only one variable is in play.

for (int i = 0; i < n; i++) { /* O(1) */ }   // O(n)
for (int j = 0; j < n; j++) { /* O(1) */ }   // O(n)
// total: O(n) + O(n) = O(2n) = O(n)  — constants drop out

A loop that shrinks the problem by a constant factor each iteration (not a constant amount) is O(log n). Halving is the classic case — binary search, or any “throw away half the remaining input” loop.

int hi = n;
while (hi > 1) {
    hi /= 2;      // problem size shrinks by a *factor* of 2 each time
    // O(1) work
}
// how many times can you halve n before reaching 1? log2(n) times → O(log n)

The distinguishing test: does the loop variable move by a fixed amount (i++, → linear, O(n)) or by a fixed factor (hi /= 2, → logarithmic, O(log n))? Confusing the two is the most common on-the-spot complexity mistake.

flowchart TD
    Q{"What does the code do?"}
    Q -->|"loop inside a loop, both scale with n"| Mult["Multiply: O(n) × O(m) = O(n·m)"]
    Q -->|"loop, then another loop (not nested)"| Add["Add, then take the dominant term: O(n) + O(m) → O(max(n,m))"]
    Q -->|"loop divides the remaining problem by a constant factor each step"| Log["O(log n)"]
    Q -->|"recursive call(s) that shrink input, plus O(f(n)) work per call"| Rec["Solve the recurrence T(n) = a·T(n/b) + O(f(n))"]

Recurrence relations for recursive code

Recursive code isn’t analyzed by “counting loops” — it’s analyzed by writing a recurrence relation: how much work does one call do outside its recursive calls, and how many smaller subproblems does it recurse into?

The general form, and the informal (not rigorously-proved) intuition behind the Master Theorem for T(n) = a·T(n/b) + O(f(n)):

a = how many subproblems each call spawns.
n/b = the size of each subproblem (input shrinks by a factor of b).
f(n) = the work done outside the recursive calls, at each level (e.g. merging).

Compare f(n) (work per level) against n^(log_b a) (how the number of leaves grows): whichever dominates determines the answer. In practice, most interview recursions fall into one of these buckets:

Recurrence	Example	Result
`T(n) = 2T(n/2) + O(1)`	binary tree traversal shape, no merge work	O(n)
`T(n) = 2T(n/2) + O(n)`	merge sort — split in half, O(n) work to merge	O(n log n)
`T(n) = T(n/2) + O(1)`	binary search — one half discarded, O(1) work per call	O(log n)
`T(n) = 2T(n-1) + O(1)`	naive recursive Fibonacci — input shrinks by a constant, not a factor	O(2ⁿ)
`T(n) = T(n-1) + O(n)`	selection sort written recursively	O(n²)

Worked derivation for merge sort, T(n) = 2T(n/2) + O(n): draw the recursion as a tree. At the top level there’s O(n) merge work. That level splits into 2 calls of size n/2, each doing O(n/2) merge work — 2 × O(n/2) = O(n) again. This repeats at every level: every level of the tree does O(n) total work, and the tree has log₂ n levels (since the input halves each level, down to size 1). Total work = O(n) per level × log n levels = O(n log n).

flowchart TD
    L0["level 0: 1 call, size n → O(n) merge work"]
    L1["level 1: 2 calls, size n/2 each → 2·O(n/2) = O(n) merge work"]
    L2["level 2: 4 calls, size n/4 each → 4·O(n/4) = O(n) merge work"]
    L3["...  log₂n levels total, each doing O(n) work..."]
    Lbottom["bottom: n calls, size 1 → base case"]
    L0 --> L1 --> L2 --> L3 --> Lbottom
    Total["total = O(n) work/level × log n levels = O(n log n)"]
    Lbottom -.-> Total

Contrast with naive recursive Fibonacci, T(n) = 2T(n-1) + O(1): the input only shrinks by 1 each call (a constant amount, not a factor), so the recursion tree has depth n, and because it branches by 2 at every one of those n levels, the tree has roughly 2ⁿ leaves — exponential, because nothing is being thrown away, every subproblem is being fully re-solved from scratch (this is exactly the motivating example for memoization / Dynamic Programming).

Amortized analysis: the dynamic array doubling argument

A dynamic array (Java ArrayList, Python list) claims O(1) append, but every so often, when the backing array is full, append has to allocate a new, larger array and copy every existing element into it — an O(n) operation. Amortized analysis is the argument for why this is still O(1) on average, over any long sequence of appends, even though individual appends are sometimes expensive.

The key design choice: the array doubles in capacity on resize (not “adds 10 more slots”). Walk it with real numbers, starting from capacity 1, appending 16 elements:

Append #	Capacity before	Resize?	Copy cost	Cumulative total cost	Cumulative cost ÷ n
1	1	no (fits)	0	1	1.0
2	1	yes → 2	1	1 + 1 + 1 = 3	1.5
3	2	yes → 4	2	3 + 2 + 1 = 6	2.0
4	4	no	0	7	1.75
5	4	yes → 8	4	7 + 4 + 1 = 12	2.4
6–8	8	no	0	15	1.875
9	8	yes → 16	8	15 + 8 + 1 = 24	2.67
10–16	16	no	0	31	1.94

(“cost” of each append itself is 1; a resize additionally pays a copy cost equal to the number of elements copied.) By append #16, total cost is 31 for 16 appends — ≈2 per append, not growing with n. This isn’t a coincidence: the total cost of all resizes up to n appends is 1 + 2 + 4 + 8 + ... + n ≈ 2n (a geometric series that sums to roughly double the final size), so 2n total resize cost spread over n appends is O(1) amortized per append. This is why the doubling factor matters — growing by a fixed increment (e.g. always +10 slots) instead of a fixed factor would make resizes happen O(n) times instead of O(log n) times, and the geometric series argument breaks down into O(n) amortized per append instead of O(1).

flowchart LR
    C1["cap 1<br/>[a]"] -->|append, full → resize to 2, copy 1| C2["cap 2<br/>[a,b]"]
    C2 -->|append, full → resize to 4, copy 2| C4["cap 4<br/>[a,b,c,_]"]
    C4 -->|3 free appends, no copy| C4b["cap 4<br/>[a,b,c,d]"]
    C4b -->|append, full → resize to 8, copy 4| C8["cap 8<br/>[...5 used]"]
    Note["copy cost doubles each resize, but resizes get exponentially rarer —
total copy cost across n appends is O(n), so O(1) amortized per append"]

Java snippets by complexity class

// O(1) — constant, independent of n
int firstElement(int[] arr) { return arr[0]; }
 
// O(log n) — halves the search space each step
int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
 
// O(n) — single pass
int sum(int[] arr) {
    int total = 0;
    for (int x : arr) total += x;
    return total;
}
 
// O(n log n) — n calls layered over log n levels (see merge sort recurrence above)
void mergeSort(int[] arr, int lo, int hi) { /* split O(log n) levels, O(n) merge work per level */ }
 
// O(n^2) — nested loop over the same n
boolean hasDuplicatePair(int[] arr) {
    for (int i = 0; i < arr.length; i++)
        for (int j = i + 1; j < arr.length; j++)
            if (arr[i] == arr[j]) return true;
    return false;
}
 
// O(2^n) — naive recursion, input shrinks by a constant, branches by 2
long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Python snippets by complexity class

# O(1) — constant
def first_element(arr: list[int]) -> int:
    return arr[0]
 
# O(log n) — halves the search space each step
def binary_search(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
 
# O(n) — single pass
def total(arr: list[int]) -> int:
    return sum(arr)  # sum() itself is a single O(n) pass internally
 
# O(n log n) — Python's built-in sort (Timsort)
def sorted_copy(arr: list[int]) -> list[int]:
    return sorted(arr)
 
# O(n^2) — nested loop over the same n
def has_duplicate_pair(arr: list[int]) -> bool:
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False
 
# O(2^n) — naive recursion, input shrinks by a constant, branches by 2
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Complexity classes at scale (n = 1,000,000)

Growth rate differences are abstract until you plug in a real n. This is the table to have memorized for an interview gut-check on whether a proposed approach will actually finish in time:

Complexity	Name	Operations at n = 1,000,000	Feels like
O(1)	constant	1	instant, regardless of input size
O(log n)	logarithmic	≈ 20	instant — binary search through a million items in ~20 steps
O(n)	linear	1,000,000	one pass — fine, runs in well under a second
O(n log n)	linearithmic	≈ 20,000,000	still fast — the ceiling for comparison-based sorting
O(n²)	quadratic	1,000,000,000,000 (10¹²)	too slow — this alone would take minutes to hours
O(2ⁿ)	exponential	astronomically larger than atoms in the observable universe	never finishes for anything but tiny n

The practical rule of thumb this table justifies: for n up to ~10⁵–10⁶, an O(n log n) or better solution is required; O(n²) is usually only acceptable for n up to a few thousand. When an interview problem states n ≤ 10⁵ in its constraints, that’s a direct signal the intended solution is not the brute-force O(n²) one.

Complexity comparison

Approach shape	Time	When it applies
Nested loops, both over the full input	O(n²)	Brute-force pair/subarray checks
Sequential (non-nested) loops	O(n + m) → simplifies to O(max(n, m))	Two independent passes over possibly different-sized inputs
Loop that halves remaining input each step	O(log n)	Binary search, and any “discard half” strategy
Divide-and-conquer, `a` subproblems of size `n/b`, `O(n)` merge work	O(n log n) when `a = b` (e.g. merge sort)	Split, recurse, combine
Recursion where input shrinks by a constant and branches	O(2ⁿ) (or worse)	Naive recursive Fibonacci/subset-sum without memoization
Dynamic array append (doubling growth)	O(1) amortized, O(n) worst case for a single call	Any language’s growable array/list under the hood

Common pitfalls

Dropping constants but not dropping the wrong ones: O(2n) simplifies to O(n) — but be careful not to over-apply this reflex to constants that actually matter in practice (a solution that’s O(n) with a large hidden constant factor, e.g. running 50 passes over the array, can be slower in the real world than an O(n log n) solution with a tiny constant, even though Big-O formally ranks the latter “worse”).
Treating “amortized O(1)” as “always O(1)”: a single call to append right when the array is full is genuinely O(n) — amortized analysis is a statement about a sequence of operations, not a guarantee on any individual call. This distinction matters in real-time/latency-sensitive systems where one slow call, even if rare, can matter.
Confusing “shrinks by a constant amount” with “shrinks by a constant factor”: n → n-1 each call is linear recursion depth (O(n) calls); n → n/2 each call is logarithmic depth (O(log n) calls). Mixing these up is the single most common recurrence-analysis mistake.
Forgetting space complexity of the call stack in recursion: a recursive solution with O(n) depth uses O(n) space on the call stack even if it does no other extra allocation — easy to state a recursive solution as “O(1) extra space” and be wrong.
Analyzing average-case when the question asks for worst-case (or vice versa): hash map lookup is O(1) average but O(n) worst case (see Hashing & Hash Maps) — stating just “O(1)” without qualifying which case can read as imprecise in an interview.
Ignoring input-size constraints when picking an approach: if the problem states n ≤ 20, an O(2ⁿ) brute force is intended and fine; reaching for a complicated O(n log n) solution isn’t “better,” it’s solving a different problem than the one asked.

Practice problems

Problems where nailing the complexity analysis (not just getting a correct answer) is the actual point of the exercise:

Binary Search (canonical O(log n) — also the base case for proving why “sorted + narrowing” collapses to logarithmic)
Merge Sort / Quick Sort (recurrence-relation analysis, and why quicksort’s worst case degrades to O(n²) despite average-case O(n log n))
Fibonacci Number — naive recursive vs. memoized vs. bottom-up (O(2ⁿ) → O(n) → O(n), O(1) space with two variables — the textbook memoization motivator, see Dynamic Programming)
Climbing Stairs (same recurrence shape as Fibonacci, good for practicing recognizing the pattern under a different problem statement)
Pow(x, n) — fast exponentiation by repeated squaring (O(log n) instead of the naive O(n) loop of multiplications)
Counting Bits (spotting the O(n) DP relation between i and i >> 1, instead of an O(n log n) per-number bit count)
Two Sum — brute force O(n²) vs. hash map O(n) (the standard “state both, justify the upgrade” interview beat)

Interview angles

“Walk me through how you got O(n log n) for that.” — don’t just state the answer; write the recurrence (T(n) = 2T(n/2) + O(n)) and either sketch the recursion-tree level-by-level argument or invoke the Master Theorem by name with its three components (a, b, f(n)).
“Is append/add really O(1)?” — no, it’s O(1) amortized; be ready to give the doubling-cost argument with real numbers (the geometric series summing to ~2n total copy cost over n appends), and know that a single call can be O(n) in the worst case.
“Your solution is O(n²) — is that actually a problem here?” — check the stated constraints first; O(n²) is fine for n in the thousands, a hard blocker for n in the millions. A strong answer ties the complexity claim back to the problem’s stated input bounds instead of treating Big-O as an abstract exercise.
“What’s the space complexity of your recursive solution?” — don’t forget the call stack; O(n) recursion depth is O(n) space even with zero extra data structures allocated.
“Big-O gives the same answer for two approaches — how do you choose?” — talk about constant factors, cache locality, and real-world input distribution (e.g. an O(n) solution with 10 passes vs an O(n log n) with 1 pass can go either way depending on actual n) — Big-O is an asymptotic tool, not the whole performance story.
“When does average-case and worst-case diverge, and why does it matter?” — hash maps (O(1) avg / O(n) worst under adversarial collisions), quicksort (O(n log n) avg / O(n²) worst on already-sorted input with a naive pivot) — name a mitigation (good hash function / randomized pivot) rather than just acknowledging the gap exists.

Notes

Explorer