Big-O Without the Panic

Big-O Is a Promise About Growth, Not a Stopwatch

Big-O does not tell you how many milliseconds your code takes. It tells you how the work grows as the input gets bigger. That distinction is the whole game. A function that runs in 2 microseconds on 10 items but 40 seconds on 10 million items has a growth problem, and no faster laptop saves you from it.

So stop reading Big-O as "speed." Read it as: if I double the input, what happens to the work? That single question answers almost everything you need in an interview or a code review.

You care about growth because inputs in the real world get large without asking permission. Your user table grows. Your log file grows. The array of orders you loop over on every request grows. Code that felt instant in testing falls over in production not because it got slower, but because n got bigger and your algorithm's growth curve caught up with you.

Count the Work, Ignore the Noise

To estimate complexity, count how many times the dominant operation runs as a function of input size n. Then throw away two things: constant factors and lower-order terms.

Throwing away constants means O(2n) and O(n) are the same class. Doing two passes over a list instead of one does not change the growth story. Throwing away lower-order terms means O(n^2 + n) is just O(n^2) — once n is large, the squared term dwarfs everything else and the rest is rounding error.

This feels like cheating. It is not. Big-O deliberately blurs detail so you can compare algorithms at the level that actually decides scaling behavior. A tighter constant matters for tuning; the growth class matters for whether your code survives at all.

Here is the reasoning applied to a loop:

def has_duplicate(nums):
    for i in range(len(nums)):          # runs n times
        for j in range(i + 1, len(nums)):  # runs ~n times each
            if nums[i] == nums[j]:
                return True
    return False

Outer loop: n iterations. Inner loop: up to n more per outer step. Multiply nested loops, so n * n = O(n^2). You did not memorize that. You counted it.

The Growth Classes You Actually Meet

There are maybe six classes worth knowing by name. Order them by how fast they grow, worst last.

O(1) — constant

The work does not depend on n at all. Indexing a list, looking up a key in a dict, appending to a list. Doubling the input changes nothing.

O(log n) — logarithmic

Every step throws away a fraction of the remaining input, usually half. Binary search is the classic case. Going from a thousand items to a billion adds only about twenty steps. Logarithmic algorithms barely notice size. When you see "halve the search space each time," think log.

O(n) — linear

You touch each item a constant number of times. One loop over the array. Summing a list, finding a max, a single pass. Double the input, double the work. This is usually the best you can do when you genuinely have to look at everything.

O(n log n) — linearithmic

You do linear work, but log n times over — or a log-depth process that touches all n items at each level. Good sorting algorithms live here. If a problem seems to need sorting, n log n is often the floor.

O(n^2) — quadratic

Nested loops over the same input. Comparing every pair. Fine for small n, a trap for large n. The has_duplicate above is quadratic — and there is a linear rewrite using a set, which is exactly why hash maps are your default tool later in this book.

O(2^n) and O(n!) — exponential and factorial

The work explodes. These show up in naive recursion that re-solves the same subproblems, and in "try every combination" brute force. Usually a signal to reach for memoization or a smarter structure.

A rule of thumb worth internalizing: sequential steps add, nested steps multiply. Two separate loops over the array are O(n) + O(n) = O(n). One loop inside another is O(n) * O(n) = O(n^2). Almost all loop analysis reduces to spotting which of those two you are looking at.

Recursion: Read the Branching and the Depth

Recursion feels harder to analyze, but it is the same counting with two questions: how many times does the function call itself, and how deep does it go?

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Each call spawns two more, and the tree goes n deep. Two-way branching over depth n is roughly O(2^n) — which is why naive fib crawls past n = 40. Now compare a recursion that halves the input each call, like binary search: one branch, depth log n, so O(log n). Same tool, wildly different cost, and you can see it from the shape of the calls.

Do not forget space. Recursion uses the call stack, so depth is a memory cost. That halving binary search is O(log n) space; a recursion n deep is O(n) space even if it does little work per call. Space complexity follows the same growth logic — count the extra memory you allocate as n grows, drop the constants. An in-place swap is O(1) space; building a new list of size n is O(n).

If you want to drill the recursion tracing until the branching is second nature, /courses/dsa-python and /courses/advanced-python-programming both have interactive playgrounds for it.

The panic around Big-O comes from treating it as trivia to memorize. It is not trivia. It is a habit: name the input, count the dominant work as it scales, keep only the fastest-growing term, and check the memory the same way. Do that by inspection and the notation stops being a wall and starts being a shortcut for the thing you already reasoned out.