Complexity & Big-O: Measuring How Work Grows

What you'll learn

• Why we judge an algorithm by how its work grows, not by seconds on your laptop
• How to count steps and write the result in Big-O notation
• The common growth classes: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)
• How to read the complexity straight off a loop, and how to spot hidden costs
• You will feel it: a slow idea that times out on a big input, and the fast idea that passes instantly

The phone book problem 📖

Imagine a paper phone book with 1,000,000 names and you want to find "Omar".

• Method A: start at page one and check every name until you find him. In the worst case that is 1,000,000 checks.
• Method B: open the book in the middle. "Omar" comes after the name you see? Throw away the first half. Repeat on what is left. This needs only about 20 checks.

Now the city doubles to 2,000,000 names. Method A needs up to 2,000,000 checks. Method B needs one more check (21).

That is the whole idea of complexity: not "how fast is it today?" but "what happens to the work when the problem gets bigger?" Computers get faster every year, but a better algorithm beats a faster machine as soon as the input is large enough.

Big-O is the shorthand we use to talk about it. Method A is O(n) (work grows in step with the number of names). Method B is O(log n) (work grows only by one step each time the input doubles).

Big-O in one page

We count steps (a comparison, an addition, an array read) as a function of the input size n. Then we keep only the term that grows fastest and throw away constant multipliers:

3n² + 50n + 7   →   O(n²)

Why throw things away? For big n the n² term dwarfs everything else, and the constant (3) depends on the machine and the language, not on the idea. Big-O compares ideas, not computers.

Big-O is an upper bound on growth. Unless we say otherwise we quote the worst case: the item is last, or missing.

The ladder, from best to worst:

• O(1) constant: read a[5], push onto a stack, look up a key in a hash map (on average)
• O(log n) logarithmic: halve the problem each step, like the phone book (binary search)
• O(n) linear: one pass over the data (sum, maximum, linear search)
• O(n log n): efficient sorting (merge sort, the built-in sort)
• O(n²) quadratic: every pair of items, usually two nested loops
• O(2ⁿ) exponential: try every subset of n items. Hopeless beyond n of about 40

Feel the scale with n = 1,000,000:

• O(log n) is about 20 steps
• O(n) is 1 million steps
• O(n log n) is about 20 million steps
• O(n²) is 1,000,000,000,000 steps: hours of computing

A rule of thumb: a compiled language does roughly 10⁸ simple operations per second, and Python tens of millions. So you can afford about n = 10⁶ for O(n log n) but only n of a few thousand for O(n²) if you want the answer in a second or two.

Reading complexity off the code

You rarely need math. Look at the loops.

One loop over the data is O(n):

def total(a):
    s = 0
    for x in a:        # runs n times
        s += x         # 1 step each
    return s

A loop inside a loop multiplies, O(n²):

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

The inner loop runs (n-1) + (n-2) + ... + 1 + 0 times, which is n(n-1)/2. Drop the constant and the smaller term: O(n²).

A loop that halves (or doubles) its variable is O(log n):

def halvings(n):
    steps = 0
    while n > 1:
        n //= 2        # 1,000,000 -> 500,000 -> 250,000 -> ... -> 1
        steps += 1
    return steps

Four rules that cover most code:

1. Blocks one after another add, and the biggest wins: O(n) + O(n²) is O(n²).
2. Nested blocks multiply: a loop of n running an O(m) step is O(n·m).
3. Different inputs get different letters. Looping over list a and then list b is O(a + b), not O(n).
4. Check what each line costs. A single line can hide a whole loop.

Hidden costs worth memorising (Python, similar elsewhere):

• x in my_list scans the list: O(n). On a set or dict it is O(1) on average.
• my_list.pop(0) and my_list.insert(0, x) shift every element: O(n).
• a[1:] copies the list: O(n). Slicing inside a loop quietly makes it quadratic.
• Building a string with s += piece in a loop can cost O(n²) overall because strings are immutable. Collect pieces in a list and "".join(pieces) once.

Trade memory for time

The cheapest way to make a slow algorithm fast is often to remember what you have already seen. Checking "have I seen this number before?" by scanning all previous numbers costs O(n) per question. A hash set answers the same question in O(1) on average, at the price of storing the numbers: O(n) extra space.

This is the most common trade in programming: spend memory to save time. Space complexity is written exactly like time complexity (it counts extra memory as the input grows).

Nested loops : O(n²) time, O(1) extra space
Hash set     : O(n)  time, O(n) extra space

Run the next demo and compare how much work each version does on the same data.

Best, average, worst, and when Big-O misleads

• Worst case is what Big-O usually quotes: linear search is O(n) because the item might be last. Its best case (item is first) is O(1).
• Average case assumes a typical input. A hash map lookup is O(1) on average, but a pathological set of keys that all collide could degrade it. Production languages defend against this.
• Amortised cost averages over a whole sequence of operations. Appending to a Python list is O(1) amortised: now and then it has to copy everything into a bigger block, but spread over many appends the cost per append stays constant.

Big-O is not the whole story:

• It hides constants. An algorithm taking 100n steps beats one taking n² steps only once n is above 100. For tiny inputs the "worse" algorithm can win.
• Two O(n) solutions can differ by a factor of 50 in real time because of memory access patterns.
• Measure before optimising. But when the input is large, growth rate beats everything else.

A solid habit for any problem: (1) write the simplest correct solution, (2) estimate its complexity, (3) compare with the input limits, (4) only then look for a better idea.

Summary

• Complexity measures how the work grows with the input size, so it compares ideas independently of hardware.
• Keep the fastest-growing term and drop constants: 3n² + 50n + 7 is O(n²).
• The ladder: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
• Read it off the code: sequential blocks add, nested blocks multiply, halving loops are logarithmic, and watch for hidden O(n) lines such as x in list, slicing and pop(0).
• A hash set trades O(n) memory for O(1) lookups and often turns O(n²) into O(n).
• Always compare your complexity with the input limits before you code.

Practice next: take any loop you wrote recently and write its complexity in a comment. Then continue with Arrays, Strings & Hash Maps, where these ideas become everyday tools.