Big-O & Time Complexity: A Practical Primer

What Big-O actually measures, the classes you will meet in interviews, and how to analyze your own code.

What Big-O measures

Big-O notation describes how the running time or memory of an algorithm grows as the input size n grows, ignoring constant factors and lower-order terms. It captures the shape of growth, not a stopwatch reading: an O(n) algorithm may be slower than an O(n²) one on tiny inputs, but as n increases the O(n) version wins, and eventually wins by a landslide.

Interviewers ask for complexity because it predicts behavior at scale. Code that is fine on 100 items can hang on 100,000 if it is quadratic. Stating the complexity also shows you understand the cost of your approach, not just that it produces the right answer.

The complexity classes, fastest to slowest

Notation	Name	Typical example
O(1)	Constant	Hash-map lookup, array index
O(log n)	Logarithmic	Binary search
O(n)	Linear	One pass over an array
O(n log n)	Linearithmic	Efficient sorting (merge / heap sort)
O(n²)	Quadratic	Nested loops over the same array
O(2ⁿ)	Exponential	Generating all subsets
O(n!)	Factorial	Generating all permutations

As a rule of thumb for a 1-second limit: O(n) and O(n log n) comfortably handle millions of elements, O(n²) is fine into the low thousands, and anything exponential is only viable for small n (roughly n ≤ 20).

How to analyze a loop

Count how many times the innermost work runs as a function of n. A single pass is linear; a loop nested inside another over the same data is quadratic; a loop that halves the remaining work each step is logarithmic.

// O(n): each element once
for (int x : nums) total += x;

// O(n^2): every pair
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        consider(nums[i], nums[j]);

// O(log n): halve the range each step
while (lo < hi) { int mid = (lo + hi) / 2; ... }

Analyzing recursion

Picture the recursion as a tree and add up the work across all nodes. Merge sort splits the input in two and does O(n) work merging at each of its O(log n) levels, giving O(n log n). Naive Fibonacci branches into two calls that mostly recompute the same values, producing an O(2ⁿ) explosion — the classic signal that memoization or dynamic programming is needed.

Space complexity

Space complexity counts the extra memory an algorithm uses beyond its input. The recursion call stack counts: a depth-first traversal of a tree of height h uses O(h) stack space even though it allocates no data structures. A common trade-off is spending O(n) space (say, a hash set) to bring time down from O(n²) to O(n).

Worst, average, and amortized

Some structures have different costs depending on the case. A hash map is O(1) on average but O(n) in a pathological worst case; quicksort averages O(n log n) but degrades to O(n²) on bad pivots. "Amortized" describes the average cost per operation across a sequence: appending to a dynamic array is O(1) amortized, even though the occasional resize is O(n), because resizes are rare enough to average out.

What interviewers want to hear

State the time and space complexity, ideally before you start coding.
Begin with a brute-force estimate, then explain how your optimization lowers it.
Name the dominant term — O(n + n²) is just O(n²); constants and lower-order terms drop.
Tie the complexity back to the constraints: if n can be 10⁵, an O(n²) plan will time out.

Once the notation feels natural, every pattern on the patterns page comes with its expected complexity, and you can sanity-check your solutions as you practice.

← Back to the prep guide