Inventing Big O Notation

You've written functions. Some are fast, some are slow. But how slow? And what happens when the input gets bigger? Let's find out by measuring.

Time both functions on lists of size 1,000, 5,000, and 10,000.

For each size, record how long each function takes. When the input gets 5× bigger (1,000 → 5,000), how much slower does each function get?

Use time.time() before and after each call to measure:

lst = list(range(1000))

start = time.time()
sum_list(lst)
print("sum_list:", time.time() - start, "seconds")

start = time.time()
has_pair_with_sum(lst, -1)
print("has_pair:", time.time() - start, "seconds")

Try the same for n = 5000 and n = 10000.

Plot time vs input size for both functions on the same graph.

Use input sizes from 100 to 5,000. What shape does each curve have?

One function's time grows proportionally to the input size. The other grows proportionally to the square of the input size.

This distinction is enormous. On a million items:

• The linear function takes ~1 second
• The quadratic function takes ~11 days

Understanding which category your algorithm falls into is one of the most important skills in programming.

Timing is noisy — it depends on your computer's speed, what else is running, even the room temperature. Can we predict how an algorithm grows without running it?

Yes: count the key operations.

Go back to sum_list and has_pair_with_sum. Add a counter variable to each one that counts how many times the innermost operation runs. Return the count along with the result.

Then run your counted versions on sizes 10, 100, and 1,000. Print the counts.

How does the count relate to n in each case?

Look at the counts from has_pair_counted. Divide each count by n, then by n².

Which ratio stays roughly constant — count/n or count/n²?

When $n = 1{,}000{,}000$, the count will be about $500{,}000{,}000{,}000$ (500 billion). Does it matter that it's $n^2/2$ instead of $n^2$? Would the "÷2" make any practical difference at that scale?

Write two functions that both loop through a list once, but one does 3× as much work per element. For example, one adds each element once, the other adds it three times.

Time both on sizes 10,000, 100,000, and 1,000,000. Compute the ratio of their times for each size.

Does the ratio stay constant or change as n grows?

We care about the growth rate, not the exact count. Whether it's $n$, $2n$, or $100n$ — they all grow at the same rate. Whether it's $n^2$, $n^2/2$, or $5n^2 + 3n$ — they all grow quadratically.

We need a shorthand that captures the growth family and throws away the constants. How would you write "this algorithm grows like n²"?

You keep saying things like "this grows like n" or "this grows like n squared." Let's make that precise.

You've already seen two growth families: one where count = n (linear) and one where count ≈ n² (quadratic). But there are others.

Try this experiment. Write a function that searches a sorted list by repeatedly cutting the search range in half:

def halving_search_counted(lst, target):
    count = 0
    lo, hi = 0, len(lst) - 1
    while lo <= hi:
        count += 1
        mid = (lo + hi) // 2
        if lst[mid] == target:
            return count
        elif lst[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return count

Run it on sorted lists of size 10, 100, 1,000, 10,000, and 100,000 (searching for -1 so it always fails). How many steps does it take each time?

The count barely grows even as n goes from 10 to 100,000. What mathematical function grows this slowly?

Steps for n=10:

Steps for n=100,000:

What function of n gives these values:

You've now discovered three growth families from real code:

There are also two more common ones:

• A function that returns lst[0] — always 1 step, regardless of n → ?
• An outer loop of n, where each iteration does a halving search (log n work) → ?

Give each growth family a descriptive one-word name.

Always the same, regardless of n:

Grows like log(n):

Grows like n:

Grows like n × log(n):

Grows like n²:

You discovered that $n^2/2$ and $n^2$ and $7n^2$ all grow the same way. The constant multiplier doesn't matter. And you discovered that when $n$ is large, $n^2 + 10n$ is basically just $n^2$ (the $+10n$ is negligible).

So to describe the growth family, we can simplify any expression by:

1. Dropping constant multipliers ($3n$ → $n$)
2. Keeping only the fastest-growing term ($n^2 + 10n$ → $n^2$)

Try it. Simplify each expression to just the growth family:

1. $5n + 3$
2. $2n^2 + 10n + 7$
3. $100$ (just the number, no $n$)
4. $n^3 + 1000n^2$
5. $3n \log n + 5n$

5n + 3 →

2n² + 10n + 7 →

100 →

n³ + 1000n² →

3n·log(n) + 5n →

You keep writing "this algorithm grows like n²" or "grows like n·log(n)." That's wordy. Invent a shorter way to write it.

Requirements for your shorthand:

• It should take a growth family (like $n^2$) and wrap it in some notation
• It should be clear that you mean "grows like ___" and not "equals exactly ___"
• It should work for all families: constant, log(n), n, n·log(n), n², etc.

Write your notation for each family. Any format you like.

Your shorthand for 'grows like 1 (constant)':

Your shorthand for 'grows like n':

Your shorthand for 'grows like n²':

Plot all five growth families on the same graph for $n$ from 1 to 100:

• O(1): $f(n) = 1$
• O(log n): $f(n) = \log_2(n)$
• O(n): $f(n) = n$
• O(n log n): $f(n) = n \cdot \log_2(n)$
• O(n²): $f(n) = n^2$

Which families look practically the same at small n? Which one towers over everything?

The notation you just invented is called Big O notation. Computer scientists write:

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n)$$

$O(f(n))$ means "grows at most as fast as $f(n)$." When we say an algorithm is $O(n^2)$, we mean: as the input gets large, the time grows no faster than some constant times $n^2$.

The formal notation was introduced by Paul Bachmann in 1894 and popularised by Edmund Landau — but the idea is exactly what you discovered: classify algorithms by their growth family, ignore the constants.

Now that you have the notation, let's practise using it. Given a piece of code, how do you figure out its Big O without running it?

What's the Big O of this function? The input is a list of length $n$.

def find_max(lst):
    best = lst[0]
    for x in lst:
        if x > best:
            best = x
    return best

How many times does the comparison x > best run?

Big O:

What about this one?

def double_scan(lst):
    total = 0
    for x in lst:       # first loop
        total += x
    for x in lst:       # second loop
        total += x * 2
    return total

The first loop does n operations, the second does another n. What's the total? What's the Big O?

Total operations:

Big O:

And this?

def all_pairs(lst):
    pairs = []
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            pairs.append((lst[i], lst[j]))
    return pairs

For each value of i, how many times does the inner loop run? What's the total across all values of i?

Big O:

What's the Big O of this?

def get_first(lst):
    return lst[0]

Big O:

You just predicted the Big O of four functions: find_max (O(n)), double_scan (O(n)), all_pairs (O(n²)), and get_first (O(1)).

Now verify your predictions. For each function, add an operation counter (like you did in Part 2). Run on sizes 100, 1,000, and 10,000. Divide the count by your predicted growth function ($n$ or $n^2$ or $1$). If your prediction is correct, the ratio should stay roughly constant as n grows.

Consider linear search — scanning a list from left to right looking for a target:

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1

1. Best case: What input makes this as fast as possible? How many comparisons?
2. Worst case: What input makes this as slow as possible? How many comparisons?
3. Average case: If the target is equally likely to be at any position, how many comparisons on average?

When someone says "linear search is O(n)" without further explanation, which case do they usually mean?

Best case — comparisons:

Worst case — comparisons:

Average case — comparisons:

O(n) usually refers to:

Rules of thumb for reading code:

Time isn't the only resource that matters. Memory (space) does too. The same Big O notation works — instead of asking "how does time grow?" we ask "how much extra memory does this algorithm need as the input grows?"

For each function, figure out how much extra memory it creates (beyond the input itself). Don't count the input list — just the new things the function allocates.

Function A:

def sum_in_place(lst):
    total = 0
    for x in lst:
        total += x
    return total

Function B:

def make_copy(lst):
    copy = []
    for x in lst:
        copy.append(x)
    return copy

Function C:

def make_matrix(n):
    matrix = []
    for i in range(n):
        row = [0] * n
        matrix.append(row)
    return matrix

For each: how many new items does it create? How does that depend on n?

Function A — new items created:

Function B — new items created:

Function C — new items created:

Create lists of increasing size and n×n matrices of increasing size. Count the number of elements in each to verify the growth pattern.

For lists: how does the element count grow with n? For matrices: how does the element count grow with n?

You need to check if a list has any duplicate values. Here are two approaches:

Approach 1 — Nested loops (no extra memory):

def has_dup_loops(lst):
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] == lst[j]:
                return True
    return False

Approach 2 — Use a set (extra memory):

def has_dup_set(lst):
    seen = set()
    for x in lst:
        if x in seen:
            return True
        seen.add(x)
    return False

1. What's the time complexity of each? (Think about the loop structure.)
2. What's the space complexity of each? (How much extra memory does each create?)
3. Which is "better"?

Approach 1 — time / space:

Approach 2 — time / space:

Which is better and why:

Every algorithm has both a time complexity and a space complexity. Now you know how to read and evaluate both. As you work through the chapters ahead, you'll see this tradeoff again and again — fast algorithms that use extra memory vs slow algorithms that work in-place.

Let's see the full picture. How long does each complexity class take on real-world input sizes?

Assume each operation takes 1 microsecond (one millionth of a second). For each complexity class, compute how many operations it takes at different input sizes, then convert to human-readable time.

Fill in this table for $n$ = 10, 1000, $10^6$, and $10^9$:

Which complexity classes are still practical at $n = 10^9$? Which ones are hopeless?

Going further:

• O(2ⁿ) — exponential: The number of subsets of a set with n items. Algorithms that try every subset are O(2ⁿ) — feasible for n ≤ 20, impossible for n = 100.
• O(n!) — factorial: The number of permutations. Even worse than exponential.
• Amortized analysis: Some operations are usually fast but occasionally slow (like appending to a Python list that needs to resize). Amortized analysis averages the cost over many operations.
• P vs NP: The biggest open question in computer science — are there problems where checking a solution is easy but finding one is fundamentally hard? A million-dollar prize awaits the answer.