Big O notation is the language engineers use to describe how an algorithm’s cost grows as the input gets bigger, and once you can read it you stop guessing about performance and start predicting it. This post skips the heavy math and instead runs real timeit measurements so you can watch O(1), O(log n), O(n), O(n log n), and O(n squared) behave exactly the way the theory says they will.

“Premature optimization is the root of all evil.”

Donald Knuth, Structured Programming with go to Statements

Last Updated: July 2026 | Tested on: Python 3.14.6 | Difficulty: Intermediate | Reading Time: 18 minutes

Here is the everyday version. Say a user named Aditi asks you to find her name in a phone book. If the book is sorted, you flip to the middle, decide left or right, and keep halving. Doubling the size of the book adds just one extra flip. Now imagine instead you read every single page from the front. Double the book and you double the work. Those two strategies have completely different shapes, and Big O is how we name that shape. It does not care that one laptop is faster than another. It cares about what happens when the input grows from a thousand rows to ten million.

The single most important idea: Big O measures growth, not speed. A slow O(n) function can beat a fast O(n squared) one the moment the data gets big enough. By the end of this post you will be able to look at a loop and name its complexity, and you will have seen the numbers that make the theory undeniable.

The ladder above ranks the complexity classes you meet in real Python code, best at the top and worst at the bottom, each with a concrete example and a verdict. Keep it in your head as a rough scale: green is what you want, orange is where you slow down, red is where your program stops finishing at all. Everything below is a walk down this ladder with measurements attached.

What Big O Actually Measures

Big O describes the upper bound on how an operation’s cost scales with the size of its input, which we call n. We deliberately throw away constants and small terms, because they stop mattering once n is large. A function that does 3n + 50 steps is still O(n), because when n is a million, the 3 and the 50 vanish into the noise. What survives is the shape of the curve.

Think of it like planning a dinner. Chopping vegetables for four guests versus four hundred is a linear job: ten times the guests, roughly ten times the chopping. But if every guest has to greet every other guest before eating, the greetings do not grow linearly, they explode. That gap between “grows steadily” and “explodes” is the whole game.

The Growth Rates, Measured

Theory is easy to nod along to and hard to believe until you see the clock. Let’s time four different operations on the same list as it grows from a thousand items to a million, using the standard-library timeit module so the numbers are honest.

📄 growth.py: time four complexity classes as n grows

import timeit, bisect

def bench(setup, stmt, number):
    return timeit.timeit(stmt, setup=setup, number=number)

sizes = [1_000, 10_000, 100_000, 1_000_000]
print(f"{'n':>10} | {'O(1) idx':>10} | {'O(log n)':>10} | {'O(n) sum':>10} | {'O(n log n)':>12}")
print("-" * 64)
for n in sizes:
    setup = f"data=list(range({n})); import bisect"
    t1 = bench(setup, "data[len(data)//2]", 200000)          # O(1): index the middle
    t2 = bench(setup, f"bisect.bisect_left(data, {n//2})", 200000)  # O(log n): binary search
    t3 = bench(setup, "sum(data)", 200)                       # O(n): touch every item
    setup2 = f"import random; data=list(range({n})); random.shuffle(data)"
    t4 = bench(setup2, "sorted(data)", 50)                    # O(n log n): sort a copy
    print(f"{n:>10,} | {t1/200000*1e6:>9.4f}us | {t2/200000*1e6:>9.4f}us | "
          f"{t3/200*1e3:>8.4f}ms | {t4/50*1e3:>9.4f}ms")

▶ Output

         n |   O(1) idx |   O(log n) |   O(n) sum |   O(n log n)
----------------------------------------------------------------
     1,000 |    0.1143us |    0.2666us |   0.0092ms |    0.1416ms
    10,000 |    0.1102us |    0.3011us |   0.0808ms |    1.9115ms
   100,000 |    0.0947us |    0.3055us |   0.7537ms |   27.5133ms
 1,000,000 |    0.0871us |    0.3303us |   9.0469ms |  552.0682ms

What happened here: Read down each column and the shapes jump out. The O(1) column barely moves: indexing the middle of the list takes about a tenth of a microsecond whether the list holds a thousand items or a million, because Python jumps straight to the slot. The O(log n) column crawls up from 0.27 to 0.33 microseconds while the data grows a thousandfold, exactly the “one extra flip when the book doubles” behavior.

The O(n) sum grows in lockstep with the input: ten times the data, roughly ten times the time (0.008ms to 9ms). And O(n log n) sorting grows a little faster than linear, which is why it climbs from a fraction of a millisecond to over half a second. Note the units: the constant and logarithmic work is in microseconds, the linear and sorting work is in milliseconds. Your exact numbers will differ from the ones here since they depend on the machine, but the shapes will be identical, and that is the whole point of Big O.

Reading Code for Complexity

You do not need a stopwatch to spot the complexity of most code. A handful of rules cover the vast majority of what you will read. Here are six worked examples with the reasoning spelled out in comments.

📄 reading_complexity.py: six patterns and how to name them

# 1. Single loop over the input -> O(n)
def total(items):
    s = 0
    for x in items:        # runs n times
        s += x             # O(1) work each time
    return s

# 2. Two SEPARATE loops -> still O(n), not O(2n) (constants dropped)
def min_and_max(items):
    lo = min(items)        # O(n)
    hi = max(items)        # O(n) again, but n + n = O(n)
    return lo, hi

# 3. Nested loop over the SAME input -> O(n squared)
def all_pairs(items):
    for a in items:        # n times
        for b in items:    # n times for each a
            print(a, b)    # n * n = O(n squared)

# 4. Halving the problem each step -> O(log n)
def count_halvings(n):
    steps = 0
    while n > 1:           # n -> n/2 -> n/4 -> ... hits 1
        n //= 2
        steps += 1
    return steps

# 5. A loop that does O(n) work inside -> O(n squared) in disguise
def dedupe_slow(items):
    result = []
    for x in items:        # n times
        if x not in result:  # 'in' on a LIST is O(n)
            result.append(x)
    return result          # n * n = O(n squared)

# 6. The same idea with a set -> O(n), because set lookup is O(1)
def dedupe_fast(items):
    seen = set()
    out = []
    for x in items:        # n times
        if x not in seen:  # set membership is O(1)
            seen.add(x)
            out.append(x)
    return out             # n * O(1) = O(n)

What happened here: Four habits carry you through almost every case. First, a single loop over the input is O(n). Second, loops that run one after another add, and since Big O drops constants, O(n) + O(n) is still O(n) (example 2). Third, a loop nested inside another loop over the same data multiplies, giving O(n squared) (example 3). Fourth, anything that repeatedly halves the remaining work is O(log n) (example 4).

The trap is example 5: it looks like a single loop, but x not in result secretly scans the whole list every time, so the real cost is n times n. Swapping the list for a set in example 6 turns that hidden O(n) check into an O(1) one and drops the whole function back to linear. That one swap is the most common real-world speedup you will ever make.

When Quadratic Bites

The reason O(n squared) deserves its own section is that it feels fine in testing and falls over in production. Small inputs hide it. Let’s prove the danger by pitting the two dedupe-style approaches against each other: a nested-loop duplicate check versus a set-based one, on inputs that double each time.

📄 quadratic.py: nested loop vs set on doubling input

import timeit

def has_dup_quadratic(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):   # nested -> O(n squared)
            if items[i] == items[j]:
                return True
    return False

def has_dup_set(items):
    seen = set()
    for x in items:                          # single pass -> O(n)
        if x in seen:
            return True
        seen.add(x)
    return False

print(f"{'n':>8} | {'O(n^2) loop':>14} | {'O(n) set':>12}")
print("-" * 40)
for n in [1_000, 2_000, 4_000, 8_000]:
    data = list(range(n))   # no duplicates: forces the worst case
    t_quad = timeit.timeit(lambda: has_dup_quadratic(data), number=5) / 5
    t_set = timeit.timeit(lambda: has_dup_set(data), number=5) / 5
    print(f"{n:>8,} | {t_quad*1e3:>12.3f}ms | {t_set*1e6:>9.1f}us")

▶ Output

       n |    O(n^2) loop |     O(n) set
----------------------------------------
   1,000 |       52.582ms |     169.3us
   2,000 |      220.163ms |     363.9us
   4,000 |      739.597ms |     674.3us
   8,000 |     2116.902ms |     978.7us

What happened here: Watch what each column does when n doubles. The quadratic loop goes 52ms, 220ms, 739ms, 2116ms: roughly four times slower every time you double the input, which is the fingerprint of O(n squared). The set version goes 169us, 363us, 674us, 978us: roughly twice as slow when you double, the fingerprint of O(n). At 8,000 items the quadratic version is already more than two thousand times slower than the linear one, and it is measured in seconds while the set finishes in under a millisecond.

Now picture 8,000 becoming 800,000 in production. The set barely notices. The nested loop would run for hours. This is why “it worked on my test data” is not the same as “it will hold up,” and why reviewers flag nested loops over the same collection on sight.

Space Complexity and Amortized Cost

Big O is not only about time. Space complexity asks the same question about memory: how does the extra memory an algorithm needs grow with the input? Summing a list with a running total is O(1) space, because you keep one number no matter how long the list is. Building a brand-new copy of the list is O(n) space, because the copy grows with the original. On a small script nobody cares, but on a service processing large batches, an accidental O(n) copy is what quietly runs you out of memory.

There is one more idea worth pinning down, because it confuses people: amortized cost. Appending to a Python list is described as O(1), yet under the hood the list sometimes has to grow its internal storage, and copying everything to a bigger block is clearly an O(n) event. The word “amortized” means the occasional expensive resize is spread out across all the cheap appends, so the average cost per append stays constant. Think of a notebook: most pages you just write on, and once in a while you photocopy everything into a bigger notebook. Averaged over hundreds of pages, each page still costs about the same. Let’s confirm it empirically.

📄 amortized.py: cost per append as the list grows

import timeit

print(f"{'n appends':>10} | {'total time':>12} | {'per append':>12}")
print("-" * 42)
for n in [100_000, 200_000, 400_000, 800_000]:
    stmt = "lst=[]\nfor i in range(N):\n    lst.append(i)"
    t = timeit.timeit(stmt.replace("N", str(n)), number=5) / 5
    print(f"{n:>10,} | {t*1e3:>10.2f}ms | {t/n*1e9:>9.1f}ns")

▶ Output

 n appends |   total time |   per append
------------------------------------------
   100,000 |       9.55ms |      95.5ns
   200,000 |      13.44ms |      67.2ns
   400,000 |      29.77ms |      74.4ns
   800,000 |      64.01ms |      80.0ns

What happened here: The total time grows in line with the number of appends, which tells you that filling a list of n items is O(n) overall. The column that proves the amortized claim is the last one: the cost per append hovers around 70 to 95 nanoseconds and does not climb as the list gets eight times bigger. If every append had to copy the whole list, that per-append number would rise steadily. It stays flat because the expensive resizes are rare and their cost is smeared across the many cheap appends between them. That flat line is what “amortized O(1)” looks like when you actually measure it.

Why Interviews Gate on This

If you are studying for coding interviews, big O notation is not optional trivia, it is the gate on the very first round. In the technical screens I have seen and sat, the interviewer almost never accepts a working solution without asking “and what is the time and space complexity?” A correct answer that is O(n squared) when an O(n log n) one exists is often marked as a fail, because the whole point of the data-structures-and-algorithms block is to check that you can reason about scale before you write the code.

The good news is the vocabulary is small and it repeats. Nearly every answer you give will be one of these phrases: O(1) for hash-map and set lookups, O(log n) for binary search and balanced-tree operations, O(n) for a single pass, O(n log n) for a sort-based approach, and O(n squared) for the brute-force nested loop you are usually expected to improve on. Say a candidate named Anvay reaches for a nested loop, notices it is O(n squared), and swaps in a set or a dictionary to get O(n).

That single move, spoken out loud, is often exactly what the interviewer is listening for. Learn to narrate the complexity of your own code and you have cleared the bar that trips up most applicants.

Common Mistakes

❌ Mistake: Treating “in” on a list as free

# Bad: membership test inside a loop, on a list -> O(n squared)
def common(a, b):
    return [x for x in a if x in b]   # 'x in b' scans list b every time

# Good: convert the lookup target to a set first -> O(n)
def common_fast(a, b):
    b_set = set(b)                    # one-time O(n) build
    return [x for x in a if x in b_set]  # each check is now O(1)

Why: x in some_list looks harmless, but it walks the list from the front until it finds a match. Put it inside a loop and you have quietly written an O(n squared) algorithm. Building a set once up front costs O(n), and after that every membership check is O(1), so the whole thing collapses to O(n). This is the single most common performance bug in beginner and intermediate Python.

❌ Mistake: Optimizing the wrong term

# Shaving constants off an O(n squared) loop is almost pointless
def process(rows):
    for i in range(len(rows)):
        for j in range(len(rows)):
            fast_inline_thing(rows[i], rows[j])   # still O(n squared)

# Changing the ALGORITHM shape is what actually pays off
def process_better(rows):
    index = build_index(rows)   # O(n) once
    for r in rows:
        lookup(index, r)        # O(1) each -> whole thing O(n)

Why: Beginners often try to speed up a slow function by micro-tuning the body of a nested loop, trimming a few operations here and there. That only touches the constant factor, which Big O ignores for a reason: on large inputs the exponent dominates everything. Making an O(n squared) loop twice as fast still leaves it O(n squared). Changing it to O(n) or O(n log n) is the win. Knuth’s warning about premature optimization cuts both ways: do not tune blindly, but when the data is big, picking the right complexity class is not premature, it is the job.

Best Practices

• Reach for the right container. If you look things up repeatedly, use a set or dict (O(1)) instead of a list (O(n)). This one habit prevents most accidental quadratic code.
• Count the nesting. One loop over the data is O(n). A loop inside a loop over the same data is O(n squared). If you see a third level, stop and rethink before you write it.
• Sort once, then exploit it. A single O(n log n) sort often unlocks O(n) or O(log n) steps afterward (two-pointer scans, binary search), which beats repeated linear searches.
• Measure before you tune. Use timeit on realistic input sizes. The complexity class tells you the shape, but only a measurement tells you whether it matters yet for your actual data.
• Remember space too. An O(n) copy inside a loop can be an O(n squared) memory pattern. Prefer streaming or generators when the input is large.

Wrapping Up

Big O notation is a lens, not a formula to memorize. It tells you the shape of a cost curve: constant work that never grows, logarithmic work that barely grows, linear work that keeps pace with the input, and quadratic work that explodes. You saw each of these on the clock, and the measurements matched the theory line for line: O(1) stayed flat across a thousandfold size increase, and the quadratic loop got four times slower every time its input doubled.

The takeaway habit is simple: when you write a loop, ask how many times it runs and what it does each time, and when a membership check or a nested loop shows up, reach for a set or a dictionary before the data grows. The math here is evergreen, it will outlast every framework, and it works the same in Python 3.14.6 as it did decades ago.

Next in this chapter we turn from analyzing cost to controlling it in practice with profiling tools that show you exactly where your program spends its time. the full series map, beginner to AI engineer, is on the Python + AI/ML tutorial series home.

Frequently Asked Questions

Try It Yourself: Name That Complexity

Cover the right column and name the time complexity of each snippet before you check yourself. Every answer here matches what you would measure with timeit, using the same rules from the reading-code section.

If you got 1, 6, and 7 right, you have internalized the most valuable distinction of all: a dictionary or set lookup is constant time, but the same lookup on a list is linear. Confusing those two is the source of most quietly slow Python.

Interview Questions on Big O Notation

The same ideas as they show up in real interviews, framed as scenarios you can practice out loud.

Q: Your function passes all tests but times out on the largest hidden case. You wrote a loop with an x in results check inside it. What is the complexity and how do you fix it?

The x in results check on a list is O(n), and running it inside a loop over n items makes the whole function O(n squared), which is exactly what blows up on the largest input. The fix is to keep a set of what you have already seen and test membership against that, turning each check into O(1) and the function into O(n). This single substitution is the most common interview rescue.

Q: What is the difference between O(n) and O(n log n), and when does it actually matter?

O(n) touches each item a constant number of times; O(n log n) does a little extra work per item that grows with the logarithm of the size, which is what sorting costs. For a million items the log factor is only about 20, so O(n log n) is roughly 20 times an O(n) pass, not a different universe. It matters when you can avoid the sort entirely, for example by using a hash map to get an O(n) solution instead of a sort-based O(n log n) one.

Q: Why do we drop constants and lower-order terms in Big O?

Because Big O describes behavior as n grows toward infinity, and there the highest-order term dominates everything else. A cost of 5n + 100 and a cost of n both grow as a straight line, so both are O(n); the 5 and the 100 change where the line sits, not its shape. Dropping them lets us compare the fundamental scalability of two algorithms without getting lost in machine-specific and input-specific details.

Q: A candidate says their algorithm is O(1) space, but it builds a dictionary that ends up holding one entry per input item. Are they right?

No. Space complexity counts the extra memory that grows with the input, and a dictionary with one entry per item grows linearly, so it is O(n) space. O(1) space would mean a fixed number of variables regardless of input size, like a running sum or a couple of pointers. Conflating “I only used one data structure” with “I used constant space” is a frequent mistake.

Q: How is list.append() O(1) if the list sometimes has to grow and copy all its elements?

It is O(1) amortized. Python over-allocates the list’s backing storage, so most appends drop into a slot that already exists in constant time. When the storage fills, it resizes and copies, an O(n) event, but it grows the capacity by a proportional amount so those resizes get rarer as the list grows. Averaged over all appends, the cost per append is constant, which you can verify by timing appends at increasing sizes and seeing the per-append number stay flat.

Q: When is an O(n squared) algorithm actually the right choice?

When n is guaranteed to stay small and the simpler code is clearer, or when the quadratic version has such a tiny constant factor that it beats a fancier algorithm on the real input sizes. Big O is about large n; for a list of ten items, a clean nested loop can be both faster and more readable than a hash-based solution with more overhead. The skill is knowing your actual data range before you decide.

Further reading: the official Python documentation is the authoritative source on this.

Related Posts

Previous: Python: Logging Levels, Handlers, Formatters

Next: Python Time Complexity: Lists, Dicts, Sets Under the Hood

Series Home: Python + AI/ML Tutorial Series