Big-O & Complexity Analysis

Why this matters more than it seems

At a Senior level, interviewers rarely ask "what's the Big-O of this?" as a standalone question — they expect you to state it unprompted as you design and again after you code, and to use it to justify why you're rejecting the brute force. Getting this reflex right is one of the cheapest, highest-leverage things you can practice.

Big-O, Big-Omega, Big-Theta (informally)

• Big-O (O) — upper bound. "This algorithm will not do worse than this, as input grows."
• Big-Omega (Ω) — lower bound. "This algorithm will not do better than this."
• Big-Theta (Θ) — tight bound. Used when the upper and lower bound match (most of the time, when people say "O(n)" in an interview, they mean Θ(n)).

In interviews, everyone is loose with notation and says "O(n)" to mean the tight bound. That's fine — just know the distinction exists so a rigorous interviewer doesn't catch you off guard.

The complexity classes you must recognize on sight

Notation	Name	Example
O(1)	Constant	Array index access, hash map get/set (average case)
O(log n)	Logarithmic	Binary search, balanced BST operations
O(n)	Linear	Single pass over an array
O(n log n)	Linearithmic	Efficient sorting (merge sort, heap sort), many divide-and-conquer algorithms
O(n²)	Quadratic	Nested loops over the same input (naive pair-finding)
O(2ⁿ)	Exponential	Naive recursive Fibonacci, brute-force subsets
O(n!)	Factorial	Brute-force permutations, traveling salesman brute force

A useful gut-check table for n = 10⁶ (a typical "large" constraint):

• O(n) → ~10⁶ ops → instant
• O(n log n) → ~2×10⁷ ops → instant
• O(n²) → ~10¹² ops → way too slow (this is the single most common reason a brute force gets rejected)

This is why, in an interview, the moment you see constraints like n <= 10^5, you should mentally rule out O(n²) and aim for O(n log n) or O(n).

Deriving complexity: loops

• Sequential loops → add their complexities: a loop that's O(n) followed by another that's O(m) is O(n + m), not O(n·m).
• Nested loops → multiply: a loop of size n containing a loop of size m is O(n·m).
• Loops with a shrinking/growing step (e.g. i *= 2) → logarithmic, since the loop runs ~log₂(n) times.

Deriving complexity: recursion

For recursive functions, draw (or imagine) the recursion tree and ask two questions: how many nodes does the tree have, and how much work happens per node?

A quick, interview-safe way to estimate without deriving recurrences formally:

• 1 recursive call, input shrinks by a constant amount (e.g. f(n-1)) → O(n) calls, so total is O(n × work-per-call).
• 1 recursive call, input halves (e.g. f(n/2)) → O(log n) calls.
• 2 recursive calls, input halves each time, plus O(n) work to combine (classic divide & conquer, e.g. merge sort) → O(n log n). This is the Master Theorem's most common interview case: T(n) = 2T(n/2) + O(n).
• 2 recursive calls, input shrinks by 1 each time (e.g. naive Fibonacci: f(n-1) + f(n-2)) → O(2ⁿ), because the tree roughly doubles in size at every level of depth.

You don't need to memorize the full Master Theorem for a coding interview — being able to reason through these four shapes covers the overwhelming majority of what comes up.

Space complexity — the part people forget

Space complexity counts extra memory relative to input, and includes:

1. Auxiliary data structures you allocate (hash maps, extra arrays, etc).
2. The call stack for recursion. A recursive solution with depth n uses O(n) space even if it allocates no other memory — this is a very common interview gotcha ("can you do this iteratively to save space?").

Example: a recursive tree traversal on a balanced tree of n nodes uses O(log n) stack space (tree height); on a completely skewed (linked-list-shaped) tree, it degrades to O(n).

Amortized analysis (know the concept, not the math)

Some operations are expensive occasionally but cheap on average. The canonical example: appending to a dynamic array (Python list.append, Java ArrayList.add) is O(1) amortized — most appends are O(1), but occasionally the array must be resized and copied, which is O(n). Spread across n appends, the total cost is O(n), so each append is O(1) amortized.

You'll see this idea again with the Union-Find data structure (path compression) and with certain sliding window / two-pointer proofs where a pointer "only moves forward n times total across the whole algorithm," making an apparently-nested loop actually O(n) overall.

Common traps to avoid

• Hidden O(n) inside a loop. E.g., checking x in some_list inside a loop over n items is O(n) per check → O(n²) overall. Checking x in some_set/some_dict is O(1) per check → O(n) overall. This single substitution (list → set/hash map) is the most common "optimize this" move in interviews (see the Arrays & Hashing topic).
• String concatenation in a loop is O(n) per concatenation in many languages (strings are immutable), so building a string with result += char in a loop is O(n²). Prefer a list/array buffer and join at the end.
• Slicing arrays/strings (arr[1:], s[i:j]) creates a new copy — O(k) where k is the slice length, not O(1). Doing this inside a loop can silently blow up your complexity.
• Forgetting that built-in sort is O(n log n), so if your target complexity is O(n), you cannot sort first — you need a different technique (e.g. hashing, counting sort, or a single pass).

Operation complexity cheat sheet

You should be able to produce this table from memory:

Structure	Access	Search	Insert	Delete
Array (unsorted)	O(1)	O(n)	O(n)*	O(n)
Dynamic array (append/pop at end)	O(1)	O(n)	O(1) amortized	O(1)
Linked List	O(n)	O(n)	O(1)**	O(1)**
Hash Map / Set	—	O(1) avg	O(1) avg	O(1) avg
Binary Search Tree (balanced)	O(log n)	O(log n)	O(log n)	O(log n)
Binary Heap	O(1) (peek)	O(n)	O(log n)	O(log n)

*inserting at an arbitrary index requires shifting elements. **assuming you already hold a reference/pointer to the node.

A preview: sometimes "optimal" isn't the obvious data structure

It's tempting to treat "reduce time complexity" and "throw a hash map at it" as the same move — and for the Majority Element practice problem below, a hash map counting occurrences does get you to O(n) time, which is a perfectly good interview answer. But it costs O(n) space, and there's a genuinely surprising O(n) time, O(1) space solution (the Boyer–Moore majority vote algorithm: track a single candidate and a counter, incrementing on a match and decrementing otherwise) that a hash map's "just count everything" instinct would never lead you to. It's worth attempting Majority Element with the explicit constraint "can you do this without any extra data structure?" before looking up the trick — the Probabilistic Algorithms & Data Structures topic revisits this exact algorithm in depth, including a real infrastructure case study (finding a single client responsible for the majority of traffic in a live request stream, without the memory budget for a hash map at all) that's the actual reason this 1981 algorithm still matters today.

How to actually state this in an interview

After coding (or even while designing), say it out loud, precisely:

"This runs in O(n) time because we make a single pass over the array, and O(n) space for the hash map we use to track seen values."

Naming both time and space, and tying the bound to the specific mechanism (the loop, the hash map) rather than a vague guess, is exactly the signal a Senior-level interviewer is listening for.