The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Algorithmic Complexity and Big O Notation

Next ►
►

In lesson 01-02 you verified with a stopwatch that finding a task in a list of a million elements takes far longer than finding it in an index. But stopwatches have a problem: their figures depend on your computer, your Python version, and even whatever else your machine happens to be running at the time. We need a way to talk about efficiency that is independent of all that, and that way is Big O notation. It is, without exaggeration, the most important vocabulary in the course: from here on, every operation of every structure will come labeled with its Big O. Give this lesson as much time as it needs.

Contents

  1. Time and space complexity: counting instead of timing
  2. Big O notation: what it means exactly
  3. The common classes, with examples in Python
  4. Comparison: how much the complexity class matters
  5. Best case, worst case, and average case
  6. Amortized cost (a brief mention)
  7. Measuring TaskFlow with timeit: theory versus the stopwatch

Time and space complexity: counting instead of timing

The central idea of algorithmic complexity is to stop measuring seconds and start counting operations. Instead of asking "how long does it take?", we ask: how many steps does the algorithm execute as a function of the input size, n?

  • Time complexity: how many elementary operations (comparisons, additions, assignments...) the algorithm performs as n grows.
  • Space complexity: how much additional memory it needs as n grows (not counting the input itself).

Let's count steps in TaskFlow's sequential search:

def find_in_list(tasks, target_id):
    for task in tasks:                # repeats up to n times
        if task["id"] == target_id:   # 1 comparison per pass
            return task
    return None

If there are n tasks and the one we want is at the end (or absent), the loop makes n passes with one comparison each: about n operations. If we double the tasks, we double the work. We say the time grows linearly with n. Its space complexity, on the other hand, is constant: whatever the list's size, the function only needs a handful of auxiliary variables.

This analysis has two virtues the stopwatch lacks:

  1. It is universal: n operations are n operations on your laptop and on a production server.
  2. It predicts the future: we know what will happen with 10 million tasks without having to try it.

Big O notation: what it means exactly

When counting operations, annoying details crop up: does the search make exactly n comparisons, or n comparisons plus n accesses to the "id" field plus 1 return, i.e., 2n + 1 operations? Big O notation's answer is: it doesn't matter. The only thing that matters is how the cost grows as n gets large.

Big O describes the order of growth of an algorithm's cost as n tends toward large values, ignoring multiplicative constants and lower-order terms.

The two simplification rules:

  1. Ignore the constants: 2n + 1 operations → O(n). 2n or 5n — it makes no difference: both double when n doubles, and that is what Big O captures.
  2. Keep the dominant term: n² + 3n + 20 → O(n²). When n = 1,000,000, the n² term contributes a trillion operations and the 3n barely three million: the lower-order terms become irrelevant.
def example(tasks):
    n = len(tasks)                 # 1 operation
    print(tasks[0])                # 1 operation
    for t in tasks:                # n operations
        print(t["title"])
    for t1 in tasks:               # n * n = n² operations
        for t2 in tasks:
            if t1["id"] == t2["id"] and t1 is not t2:
                print("duplicate id!")

Total cost: 2 + n + n². Applying the two rules: O(n²). The block that dominates is the double loop; for large n, the rest doesn't even register.

A note on rigor: formally, Big O expresses an upper bound on growth ("it grows no faster than..."). In everyday professional use — and in this course — it is employed as a synonym for "its cost grows like...", which is the practical interpretation you need.

The common classes, with examples in Python

Almost everything we will analyze in the course falls into five classes. Each one, with a real example on TaskFlow's tasks:

O(1) — constant

The cost does not depend on n. It makes no difference whether there are 10 tasks or 10 million.

def first_task(tasks):
    return tasks[0]           # indexing scans nothing

def total_tasks(tasks):
    return len(tasks)         # Python keeps the size precomputed

Accessing tasks[0], tasks[500_000], or asking len(tasks) costs the same: one step. Why access by index is O(1) is something you will understand in depth in lesson 01-05.

O(log n) — logarithmic

The cost grows with the logarithm of n: each step discards half of the data. Doubling n adds only one more step.

def binary_search(tasks_sorted_by_id, target_id):
    """Requires the tasks to be sorted by id."""
    low, high = 0, len(tasks_sorted_by_id) - 1
    while low <= high:
        mid = (low + high) // 2                # look at the middle
        mid_id = tasks_sorted_by_id[mid]["id"]
        if mid_id == target_id:
            return tasks_sorted_by_id[mid]
        elif mid_id < target_id:
            low = mid + 1                      # discard the left half
        else:
            high = mid - 1                     # discard the right half
    return None

How it works: because the tasks are sorted by id, looking at the middle one tells us which half contains the target, and the other half is discarded entirely without looking at it. With a million elements: 1,000,000 → 500,000 → 250,000 → ... → 1 in about 20 steps. It's the same trick you use when looking up a word in a paper dictionary: you open it in the middle and dismiss half the book at a glance.

O(n) — linear

The cost grows in direct proportion to n: touching every element once.

def count_pending(tasks):
    count = 0
    for task in tasks:                    # exactly n passes
        if task["status"] == "pending":
            count += 1
    return count

Our old friend find_in_list is also O(n). Any algorithm that needs to look at all the data at least once is at minimum O(n): there is no way to count the pending tasks without visiting each one.

O(n log n) — nearly linear

The class of the good sorting algorithms. Intuition: doing O(log n) work for each of the n elements, or repeatedly halving the problem while sorting at each level.

sorted_tasks = sorted(tasks, key=lambda t: t["priority"])

Python's sorted (the Timsort algorithm) is O(n log n). We won't implement it here; just remember that sorting properly costs O(n log n) — noticeably more than a scan (O(n)) but vastly less than comparing everything against everything (O(n²)).

O(n²) — quadratic

The cost grows with the square of n: typically, a loop inside another loop, both over the data. Doubling n quadruples the work.

def has_duplicate_titles(tasks):
    for i in range(len(tasks)):               # n passes
        for j in range(i + 1, len(tasks)):    # up to n passes for each i
            if tasks[i]["title"] == tasks[j]["title"]:
                return True
    return False

Every task is compared with all the following ones: around n²/2 comparisons, which by the constants rule is O(n²). With 1,000 tasks, half a million comparisons; with a million tasks, five hundred billion. Quadratic solutions are acceptable only with small data; spotting them (and knowing how to replace them — this very problem is O(n) with a set) is a classic interview skill.

Worse classes exist — O(2ⁿ), O(n!) — typical of brute-force problems; we will rarely run into them, but it's worth knowing they exist and that they are intractable even for modest n.

Comparison: how much the complexity class matters

Concrete numbers: approximate steps each class executes as n grows (assuming, to translate into time, about 10 million simple operations per second in Python):

n O(1) O(log n) O(n) O(n log n) O(n²)
10 1 3 10 33 100
1,000 1 10 1,000 10,000 1,000,000
1,000,000 1 20 10⁶ (~0.1 s) 2·10⁷ (~2 s) 10¹² (~28 hours)

Look at the last row: with a million elements, the difference between O(n) and O(n²) is the difference between a tenth of a second and more than a day. And O(log n) remains, for all practical purposes, instantaneous. This table explains why the experiment in lesson 01-02 gave the results it gave, and why the choice of structure matters so much: each structure offers its operations at different complexity classes.

graph TB
    subgraph "Cost growth as n increases"
        A["O(1): flat"] --- B["O(log n): almost flat"]
        B --- C["O(n): straight line"]
        C --- D["O(n log n): line that steepens"]
        D --- E["O(n²): parabola — takes off"]
    end

And the table we will use as a reference for the entire course — the cost of the common operations on Python's built-in structures:

Operation list dict / set
Access by index items[i] O(1) —
Access/insert by key — O(1) average
Membership test (in) O(n) O(1) average
Add at the end (append/add) O(1) amortized O(1) average
Insert/remove at the front or middle O(n) —

The qualifiers "average" and "amortized" are explained in the next two sections.

Best case, worst case, and average case

The same algorithm can cost differently depending on the luck of the data. Sequential search in TaskFlow:

  • Best case: the target task is the first one → 1 comparison → O(1).
  • Worst case: it is the last one or doesn't exist → n comparisons → O(n).
  • Average case: if every position is equally likely, about n/2 comparisons → O(n) (remember: constants like ½ are ignored).
Scenario What it describes When to use it
Best case The outcome with the most favorable data Almost never: it is unreliable information
Worst case The maximum guarantee: it will never do worse The professional default
Average case The expected behavior with typical data When the worst case is rare and the distribution is known

Unless stated otherwise, when someone gives a bare Big O they mean the worst case: it is the guarantee that lets you size systems ("it will never take longer than..."). The average case matters when the worst case is extraordinarily unlikely: the star example is Python's dict, whose lookup is O(1) on average but can degrade in vanishingly rare pathological situations (you will understand this when studying collisions in module 5). That is why the table above says "O(1) average".

Amortized cost (a brief mention)

One qualifier remains to explain: list's append is "O(1) amortized". Amortized cost is the cost averaged over a long sequence of operations: almost every append is instantaneous, but every so often one costs O(n) because the list has to reorganize itself internally; spreading that occasional cost across all the operations, it comes out to O(1) per operation.

For now, just hold on to the idea of "expensive very occasionally, cheap almost always, and constant on average". The exact why — what that reorganization is and why it pays off — is precisely one of the highlights of the next lesson (01-05), when we look at dynamic arrays.

Measuring TaskFlow with timeit: theory versus the stopwatch

Let's close the loop: theory predicts, and timeit verifies. If find_in_list is O(n), multiplying the number of tasks by 10 should multiply the time by ~10. Let's check:

import timeit

def create_tasks(n):
    return [{"id": i, "title": f"Task {i}"} for i in range(n)]

def find_in_list(tasks, target_id):
    for task in tasks:
        if task["id"] == target_id:
            return task
    return None

for n in (10_000, 100_000, 1_000_000):
    tasks = create_tasks(n)
    index = {t["id"]: t for t in tasks}
    worst = n - 1   # worst case: the last task

    t_list = timeit.timeit(lambda: find_in_list(tasks, worst), number=20)
    t_dict = timeit.timeit(lambda: index.get(worst), number=20)

    print(f"n={n:>9} | list: {t_list:8.4f} s | dict: {t_dict:.6f} s")

Typical output (your figures will vary; the proportions will not):

n=   10,000 | list:   0.0059 s | dict: 0.000002 s
n=  100,000 | list:   0.0601 s | dict: 0.000002 s
n=1,000,000 | list:   0.6088 s | dict: 0.000002 s

Reading the experiment:

  • The list column multiplies by ~10 on each row, exactly what O(n) predicts: cost proportional to n.
  • The dict column doesn't budge: O(1) in its purest form, confirming the average-case theory.
  • This is what Big O gives you and the stopwatch only hints at: in lesson 01-02 we saw that it happened; now we know how much and why, and we can predict it for any n without running anything.

From now on, this will be our method with every structure: analyze the Big O of its operations on paper and, when it adds value, confirm it with timeit.

Common Mistakes and Tips

  • Believing that O(1) means "fast" and O(n) means "slow". O(1) means "cost independent of n", not "instantaneous": an O(1) operation can be slow in absolute terms, and an O(n) with n = 20 is negligible. Big O speaks of growth, not absolute speed.
  • Forgetting Python's hidden costs. element in items looks like one operation, but it is O(n) inside; so is items.insert(0, x). An in on a list inside an O(n) loop manufactures an invisible O(n²): it is the most common performance mistake in Python (you saw it in exercise 2 of lesson 01-02).
  • Comparing algorithms by their best case. "My search sometimes gets it on the first try" says nothing useful. Analyze the worst case by default and mention the average only when you can justify it.
  • Ignoring space complexity. Building a dict index to search in O(1) spends O(n) of additional memory. It almost always pays off, but you must know you are paying that price: time and space trade off against each other constantly.
  • Tip: when in doubt about a piece of code's Big O, count the nested loops that depend on n as a first approximation (1 loop → O(n), 2 nested → O(n²)) and watch for hidden-cost operations inside them.

Exercises

Exercise 1: classifying snippets

State the time complexity (Big O, worst case) of each snippet and justify it in one sentence:

# (a)
def last_task(tasks):
    return tasks[-1]

# (b)
def uppercase_titles(tasks):
    return [t["title"].upper() for t in tasks]

# (c)
def conflicting_task_pairs(tasks):
    pairs = []
    for a in tasks:
        for b in tasks:
            if a["id"] != b["id"] and a["title"] == b["title"]:
                pairs.append((a["id"], b["id"]))
    return pairs

# (d)
def id_exists(tasks, target_id):
    return any(t["id"] == target_id for t in tasks)

Exercise 2: best, worst, and average

For the id_exists function from the previous exercise, describe its best case, worst case, and average case (assuming that when the target id exists, it sits at a uniformly random position). Give the Big O of each.

Exercise 3: prediction and empirical verification

has_duplicate_titles (seen in the O(n²) section) compares each task with the following ones. (a) Predict: if with n = 1,000 it takes t seconds, roughly how long will it take with n = 2,000 and with n = 4,000? (b) Verify it with timeit using tasks whose titles are all distinct (worst case: it finds nothing and compares everything). (c) Rewrite the function with a set so it is O(n) and repeat the measurement.

Solutions

Solution 1:

  • (a) O(1): access by index (even the last one, [-1]) scans nothing.
  • (b) O(n): the comprehension visits each task exactly once. (Note: it also spends O(n) of space, because it creates a new list.)
  • (c) O(n²): two complete nested loops over the n tasks → n² comparisons.
  • (d) O(n): any with a generator checks task by task and stops at the first match, but in the worst case (no match) it goes through all of them.

Solution 2:

  • Best case: the target id is in the first position → 1 comparison → O(1).
  • Worst case: the id doesn't exist (or is last) → n comparisons → O(n).
  • Average case: uniform position → n/2 expected comparisons → O(n) (the constant ½ is dropped). The typical conclusion: best case O(1), but the algorithm "is" O(n), because by default we speak of the worst case.

Solution 3:

(a) O(n²) implies that doubling n quadruples the time: with n = 2,000 it will take ~4t; with n = 4,000, ~16t.

(b) and (c):

import timeit

def has_duplicate_titles_v2(tasks):
    seen = set()
    for t in tasks:                     # n passes
        if t["title"] in seen:          # O(1) average on a set
            return True
        seen.add(t["title"])            # O(1) average
    return False                        # total: O(n)

for n in (1_000, 2_000, 4_000):
    tasks = [{"id": i, "title": f"Task {i}"} for i in range(n)]
    t_v1 = timeit.timeit(lambda: has_duplicate_titles(tasks), number=3)
    t_v2 = timeit.timeit(lambda: has_duplicate_titles_v2(tasks), number=3)
    print(f"n={n}: O(n²) {t_v1:.3f} s | O(n) {t_v2:.5f} s")

Typical result: the quadratic version follows the predicted ×4 progression (for example 0.1 s → 0.4 s → 1.6 s), while the set version merely doubles (×2 progression, linear) and is hundreds of times faster already at n = 4,000. Theoretical prediction and measurement agree: that is exactly what Big O promises. (The cost of the trade: v2 uses O(n) extra memory for the seen set.)

Conclusion

You now command the central vocabulary of the course: time and space complexity count operations and memory as a function of n; Big O notation captures the order of growth, ignoring constants and lower-order terms; the classes O(1), O(log n), O(n), O(n log n), and O(n²) cover almost everything we will analyze, with differences ranging from "instantaneous" to "more than a day" on large data; the default analysis is the worst case, reserving the average and amortized cost for when they are justified; and timeit lets you empirically confirm what theory predicts.

One debt from this lesson remains outstanding: why is access items[i] O(1)? And what mysterious reorganization makes append only O(1) amortized? The answers lie one level down, in how data is physically organized in memory. That is the topic of the next lesson: arrays and memory, the foundation everything else is built on.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved