Big-O notation explained: time and space complexity for interviews

Big-O notation describes how the running time (or memory) of an algorithm grows as the input size grows. It ignores machine speed and small details and focuses on the shape of the growth. It is the common language of coding interviews and a very practical tool for choosing between approaches.

What does O(n) mean?

If an input has n items and the work grows in proportion to n, the algorithm is O(n), "order n" or "linear". Double the input and the time roughly doubles.

Big-O describes the upper bound on growth for large inputs, usually for the worst case, and drops constants and lower-order terms:

• 3n + 10 becomes O(n).
• n² + 5n + 2 becomes O(n²).

Common complexities, fastest to slowest

Big-O	Name	Example
O(1)	Constant	Read an array element by index, hash map lookup (average)
O(log n)	Logarithmic	Binary search
O(n)	Linear	Scan a list once
O(n log n)	Linearithmic	Efficient sorting (merge sort, typical built-in sorts)
O(n²)	Quadratic	Nested loops over the same list, simple sorts
O(2ⁿ)	Exponential	Naive recursive subsets or naive Fibonacci
O(n!)	Factorial	Generating all permutations

For large n, the gap is enormous. With n = 1,000,000, O(n) is about a million steps while O(n²) is a trillion.

How to analyse code

Single loop over n items is O(n).

for (const x of items) { total += x; }     // O(n)

Nested loops multiply.

for (const a of items) {
  for (const b of items) { compare(a, b); }   // O(n * n) = O(n²)
}

Two loops one after another add, and you keep the larger term.

for (...) {...}   // O(n)
for (...) {...}   // O(n)
// total O(n + n) = O(n)

Halving the problem each step is O(log n).

while (lo <= hi) { mid = (lo + hi) >> 1; ... }   // binary search, O(log n)

Different inputs get different letters. Looping over list A (size a) and list B (size b) is O(a + b), and nested is O(a * b). Do not call both n.

Recursion: count how many calls happen and the work in each. A function that calls itself twice per level to depth n is about O(2ⁿ). Memoization (caching results) can reduce it a lot.

Space complexity

Space complexity measures extra memory used as input grows.

• A few variables: O(1).
• A new array or hash map holding up to n items: O(n).
• Recursion uses stack space: depth d means O(d).

Often you can trade space for time. A hash set lets you check duplicates in O(n) time with O(n) space, instead of O(n²) time with O(1) space.

Best, average and worst case

• Worst case is what Big-O usually reports: the slowest scenario.
• Average case is the typical behaviour.
• Amortised cost averages out an occasional expensive step. Appending to a dynamic array is O(1) amortised even though resizing sometimes costs O(n).

Example: quicksort is O(n log n) on average but O(n²) in the worst case.

Complexity of common operations

Structure	Access	Search	Insert	Delete
Array	O(1)	O(n)	O(n)	O(n)
Hash map / set (average)		O(1)	O(1)	O(1)
Linked list	O(n)	O(n)	O(1) at a known node	O(1) at a known node
Balanced search tree		O(log n)	O(log n)	O(log n)
Heap			O(log n)	O(log n) for the top

Using Big-O in interviews

1. Start with a brute-force solution and state its complexity.
2. Look for waste: repeated work, unneeded sorting, repeated searching.
3. Improve with a better data structure (hash map, set, heap) or a pattern (two pointers, sliding window, binary search).
4. State the time and space complexity of your final solution out loud, and explain the trade-off.
5. Consider constraints: if n is up to 100, O(n²) may be fine; if 10⁶, you need about O(n log n) or better.

A rough rule: a typical machine does on the order of 10⁸ simple operations per second, so an O(n²) solution with n = 10⁵ is too slow.

Common misunderstandings

• Big-O is not an exact time. A fast O(n²) can beat a slow O(n) for small inputs.
• Constants matter in real systems, even though Big-O ignores them.
• Built-in functions have their own costs. A call like list.includes(x) inside a loop hides another O(n).
• String concatenation in a loop can be O(n²) in some languages.

Takeaway: Big-O shows how cost grows with input. Learn the common classes, count loops and recursion, remember space too, and always state complexity when you explain a solution.

---

Interview prep and DSA series, Part 1 (core patterns): 1 of 5.