Big-O in Plain English

What Big-O actually measures

Big-O notation describes how an algorithm's cost grows as its input gets bigger. That's it. It deliberately ignores your laptop's speed, the programming language, and small constant factors, because those change from machine to machine. What doesn't change is the shape of the growth: double the input, and does the work double, quadruple, or barely move?

"Cost" usually means one of two things:

• Time complexity — roughly, how many basic steps the algorithm takes.
• Space complexity — how much extra memory it needs beyond the input itself.

Interviewers default to worst case: the input arrangement that makes your algorithm work hardest. Unless someone says "average case," assume worst case.

The common classes, with real numbers

The fastest way to build intuition is to plug in a concrete input size. Here is what each class costs at n = 1,000:

Notice the cliff between O(n log n) and O(n^2). At n = 1,000 that's 10,000 steps versus a million — a 100x gap that keeps widening as n grows. Most interview problems are exactly this fight: the obvious solution is O(n^2), and the expected one is O(n) or O(n log n).

The three rules for computing Big-O

1. Sequential steps add — keep only the biggest. If your code does an O(n) pass, then a separate O(n log n) sort, the total is O(n + n log n) = O(n log n). The slower phase dominates.

2. Nested steps multiply. A loop over n items that does an inner loop over n items is O(n * n) = O(n^2). A loop over n items that does an O(log n) binary search each time is O(n log n).

3. Drop constants and lower-order terms. O(3n^2 + 10n + 500) is just O(n^2). Big-O only cares about growth shape, and for large n the n^2 term swamps everything else.

A quick worked example:

def has_pair_with_sum(nums, target):      # n = len(nums)
    for i in range(len(nums)):            # runs n times
        for j in range(i + 1, len(nums)): # runs up to n times
            if nums[i] + nums[j] == target:
                return True
    return False

Nested loops over the same array: O(n^2) time. It uses no extra memory beyond a couple of loop variables, so space is O(1).

Space complexity: the part people forget

Space complexity counts the extra memory your algorithm allocates — hash maps, result arrays, copies. Two details trip people up:

• The input doesn't count, but a copy of the input does. Sorting a copy costs O(n) space.
• The recursion stack counts. A recursive function that goes n calls deep uses O(n) space even if it allocates nothing else. This is why "recursive DFS on a tree" is O(h) space, where h is the tree's height.

Amortized cost: expensive sometimes, cheap on average

Some operations are usually cheap but occasionally expensive. Appending to a dynamic array (a Python list, a JavaScript array) is the classic case: most appends take one step, but when the array fills up, it copies everything to a bigger block — an O(n) event. Because doublings are rare, the average cost per append over many appends is still constant. We call that amortized O(1): the occasional spikes flatten out when spread across all the operations.

Reading the constraints like an interviewer

Problem constraints quietly tell you which complexity is expected. A typical machine handles very roughly 10^7 to 10^8 simple operations per second, so:

If n can be 100,000 and your plan is O(n^2), that's 10^10 steps — minutes of compute. The constraint just told you to find something faster before you write a line of code.

Saying it out loud, unprompted

Mid-level interviews expect you to state complexity without being asked — once when you propose an approach, and again when you finish coding. A simple script:

"Brute force is O(n^2) because I'd check every pair. Instead I'll use a hash map, which makes each lookup O(1), so the whole thing is O(n) time and O(n) space — I'm trading memory for speed."

Two habits make this automatic. First, name the complexity of the brute force before improving it — it shows you know what you're beating. Second, always give both time and space. "O(n) time, O(1) space" takes two seconds to say and answers the follow-up question before it's asked.