All through the course we have been leaving claims on account: that nesting two loops quadruples the work when the data doubles (03-03), that binary search resolves in twenty comparisons what costs a linear search a million (06-01), that sorted is 3,600 times faster than our bubble sort (06-02) and that naive Fibonacci "explodes" (06-03). They all talk about the same thing: how much a program costs according to the size of its data. This lesson finally gives you the vocabulary to say it precisely.

That vocabulary is called Big-O notation, and it is one of those tools that change the way you look at code: once you have it, you can open a function you did not write and know, without running it, whether it will hold up with a thousand items or two hundred thousand. You will also learn the opposite, which matters just as much: when nothing needs optimising at all.

1. Why it is not measured in seconds
2. What gets counted instead
3. Big-O notation and how it is simplified
4. A catalogue of complexities
5. The growth table
6. How to analyse a piece of code
7. Three EasyTask fragments analysed
8. Worst case, best case and average case
9. Space complexity and the time-memory trade-off
10. Cost of the usual operations in Python
11. When to optimise and when not to
12. EasyTask with 20 tasks and with 200,000
13. Common mistakes and tips
14. Exercises
15. Module conclusion

In 06-02 we measured bubble sort with time.perf_counter() and got 11 seconds for 10,000 elements. It is a useful figure, but it communicates nothing outside that specific moment, because it depends on:

• The machine: an eight-year-old laptop and a modern server differ by a factor of ten.
• The language and its version: the same bubble sort in C is about fifty times faster than in Python.
• Whatever the computer was doing at that instant: another program, the antivirus, the browser.
• The specific data it happened to get: an almost-sorted list and a backwards one give different times.

If I tell you "my function takes 0.4 seconds", you do not know whether that is good. If I tell you "my function doubles its time every time the number of tasks doubles", you already know everything that matters: you know that with 200,000 tasks it will be 10,000 times slower than with 20, and that is true on any computer and in any language.

That is the change of mindset: instead of measuring how long it takes, we describe how what it takes grows when the data grows. It is a property of the algorithm, not of the machine.

What gets counted is elementary operations as a function of the input size, which by convention is called n. An elementary operation is one whose cost does not depend on the size of the data: an addition, a comparison, an assignment, accessing my_list[i], calling a function.

Adding up: 1 + n + n + 1, that is, 2n + 2 operations. What matters is not the exact number —it depends on how you count— but the shape of the expression: there is a term that grows with n and some extras that do not. And the first thing to understand is that n is not "how much data there is" in the abstract, but the size of whatever makes the work grow: here, the number of tasks in the agenda.

Big-O notation (or asymptotic notation) describes how the number of operations grows when n gets large, ignoring everything that stops mattering at that scale. It is written O(...) and read "of the order of".

Formally it is an upper bound: saying that an algorithm is O(n) means that its cost does not grow faster than n, except for a constant factor. And from that come the two simplification rules:

• Multiplicative constants are ignored. 3n and n are both O(n): an algorithm three times slower still doubles its time when the data doubles. The constant depends on the machine; the way it grows does not.
• Lower-order terms are ignored. In n² + 500n + 1000, when n is a million, n² is a trillion and 500n is five hundred million: the second term is 0.05% of the total. You are left with O(n²).

The practical consequence of this generosity is that Big-O does not compare two algorithms of the same shape: between two O(n) algorithms, one can be five times faster than the other and Big-O will not say so. That is what time.perf_counter() is for. Big-O answers a different, far more important question: what will happen when the data grows?

These six cover practically everything you will meet, and you already have an example of every one of them in this course:

Two of them are worth pausing on. O(1) does not mean "fast", it means "the same cost whatever the size": accessing my_list[999999] costs the same as my_list[0], because Python computes the memory address instead of sweeping. And O(log n) is almost as good as O(1): the base-2 logarithm of a million is 20, and of a billion is 30. A logarithmic algorithm barely notices the data growing.

At the other end, O(2ⁿ) is a wall: every new element doubles the total work. With n = 60 there is no computer in the world that will finish, and that is why naive Fibonacci was useless. Ordered from best to worst:

Numbers are more eloquent than curves. Approximate operations for each size:

Let us translate that last row into time, assuming ten million operations per second, which is a reasonable order of magnitude for Python:

There is the whole lesson in one table. With a million items, an O(n log n) algorithm answers while you wait and an O(n²) one never finishes in practice. And notice something crucial: with n = 10 all of them are instant. Complexity only matters when the data grows, and that observation will be section 11.

Three practical rules are enough for 95% of cases:

1. Individual statements (assignments, comparisons, index or key accesses): O(1).
2. Sequential loops add up; nested loops multiply. Two consecutive loops of n passes are n + n = 2n → O(n). A loop of n passes inside another of n passes is n × n → O(n²).
3. Take the dominant term. If a fragment does a sorted (O(n log n)) and then a sweep (O(n)), the total is O(n log n), because the larger one rules.

The calculation is 1 + n + n + n² = n² + 2n + 1, which simplifies to O(n²). And this is the most profitable design lesson of the analysis: the pair of nested loops dominates everything else. Optimising the first two loops would achieve nothing; the only change that matters is removing the nesting, which you have known how to do since 06-01 with an index.

There are two frequent traps when analysing. The first: a function call costs whatever the function costs, not O(1). If inside a loop of n passes you call sorted on the agenda, the total is n × n log n, not n. The second: the in operator over a list is O(n), so an if x in my_list inside a loop is a nested loop in disguise.

Fragment 1: summary_by_assignee (since v0.10), which counts each person's tasks with a dictionary.

A loop of n passes with O(1) work inside: O(n). It is optimal, because to count you have to look at every task at least once. The key is that counts.get(...) is O(1); if instead of a dictionary we used a list of names and an .index(), each pass would be O(n) and the total O(n²).

Fragment 2: show_list (v0.13), which sorts before printing.

sorted is O(n log n) and the sweep is O(n); the dominant term rules: O(n log n). You cannot do better while sorting is required, and that is the honest argument for not obsessing: the expensive part is not your code, it is the sorting, and the sorting is already done by Timsort.

Fragment 3: detecting duplicate titles, written the naive way.

Nested loops: O(n²). With 20 tasks that is about 190 comparisons, nothing. With 200,000 it would be twenty billion: hours of waiting. The set version, which you have known how to write since 05-03, solves the same thing in O(n):

Same result, a single loop. This is the perfect example of why the lesson matters: the second piece of code is not cleverer, it is cheaper, and the difference is only visible if you know how to count.

The very same algorithm can cost wildly different amounts depending on the specific data it gets. Three scenarios are distinguished, and you already saw them in the linear search of 06-01:

When somebody says "this algorithm is O(x)" without qualifying, they mean the worst case. It is the convention, and it has a solid reason: the worst case is a guarantee. If the worst case is O(n log n), you know it will never take longer, whatever the data does. The average case is an expectation, not a promise, and there are famous algorithms —quicksort from 06-02— with an excellent average case and a bad worst case.

Time is not the only thing that gets consumed: there is also space complexity, which measures how much extra memory an algorithm needs on top of the input data.

The last two rows are the famous time-memory trade-off: you spend memory to gain time. The memoisation case is devastating: it takes Fibonacci from O(2ⁿ) to O(n) in time, in exchange for O(n) in space. It is one of the best bargains in programming.

The inverted index is the same deal on a small scale: index_by_assignee costs O(n) to build and O(n) of memory, and in exchange every "what does Luis have?" query goes from O(n) to O(1). With one query it does not pay off; with fifteen a day, it pays for itself. And there is a third dimension the deal ignores and is worth not forgetting: the index has to be kept up to date, and that cost is code maintenance, not execution time.

This table is one of the most useful things you will take away from the module. With n = number of elements:

The rows in bold are the ones that cause real problems. insert(0, x) and pop(0) are O(n) because a list stores its elements consecutively in memory: putting something in or taking it out at the front forces every other element to shift. A loop that does pop(0) n times is O(n²) without looking like it. The standard library's answer is collections.deque, a doubly linked list where both ends are O(1).

And x in my_list is O(n) whereas x in my_set is O(1), which is the translation into this vocabulary of everything we saw in 06-01. Swapping a list for a set is the cheapest and most profitable optimisation there is: one line of code and a change of complexity.

Here comes the part that is almost never told, and it is as important as the rest. Most optimisations are not needed.

• While n is small, clarity rules. With 20 tasks, an O(n²) algorithm does 400 operations: microseconds. Rewriting that code to make it O(n) makes it harder to read in exchange for a saving nobody will notice.
• Measure before you touch. Intuition about where the slowness lives is notoriously bad. Use time.perf_counter() around the suspicious chunks and discover the bottleneck instead of assuming it. In most real programs, the time goes on the network or the disk, not on your loop.
• Optimise the complexity, not the constants. If something has to be improved, going from O(n²) to O(n) by swapping a list for a set is worth a thousand times more than saving three operations inside a loop.
• But choose well from the start when it is free. Writing if x in my_set instead of if x in my_list costs no extra effort and no readability. That is not premature optimisation: it is not spoiling the program through carelessness.

The rule that sums all this up is Donald Knuth's and it is half a century old: premature optimization is the root of all evil. Write clear, correct code; measure; and optimise only what the measurement points at. Big-O is not there so you optimise everything, but so you know what is going to happen when the data grows and spot in time what will not hold up.

Let us analyse the whole program, now at v0.14, in both scenarios.

With 20 tasks, everything is fine and there is nothing to change. That is the honest verdict, not a concession: the program is clear, correct and answers instantly. Optimising it would be wasted work.

With 200,000 tasks, on the other hand, the analysis says exactly what to touch and in what order:

1. Eliminate any O(n²), starting with the duplicate detection: the set version from section 7 fixes it in four lines. It is the only truly urgent thing.
2. Build the index just once at startup and keep it up to date on every addition and removal, instead of rebuilding it on every query. It takes assignee searches from O(n) to O(1).
3. Do not sort the whole agenda to show twenty lines. If the listing is paginated, heapq.nsmallest(20, agenda, key=sort_key) is O(n log 20) instead of O(n log n).
4. Stop loading and saving the whole file. A JSON of 200,000 tasks gets read entirely into memory every time; at that scale the answer is not a better algorithm, it is a database, which indexes, searches and saves only what changed.

Notice the order: first the bad complexities are removed, then time-memory trade-offs are applied and only at the end does the tool change. And notice what does not appear: rewriting sorted, micro-optimising the f-strings or removing functions to save calls. That would not move the needle.

Confusing "fast" with "good complexity". A well-written O(n²) algorithm can beat an O(n log n) one for small n, because the constants Big-O ignores do genuinely exist. Timsort, to look no further, sorts short stretches with insertion sort for exactly that reason.

Forgetting the cost of what you call. if title in [t["title"] for t in agenda] looks like an innocent line and is O(n) every time: it builds a whole list and sweeps it. Inside a loop, O(n²).

Believing that O(1) means instant and O(n²) means unacceptable. They are ways of growing, not speeds. O(n²) with n = 20 is perfect; O(n) with an expensive operation inside can be a disaster.

Analysing the best case without saying so. "My search is O(1) because it is normally near the front" is a half-truth. By convention we talk about the worst case, which is the one that gives guarantees.

Optimising without measuring. Changing code "because it looks slow" usually damages readability without improving the time. Measure, locate and only then act.

Tip: learn to spot nested loops. They are not always indented one inside the other. An in over a list, an .index(), a comprehension or a call to another function that sweeps are all hidden loops. Always ask yourself: does this line sweep anything?

Tip: the best change is usually of data structure, not of algorithm. List → set for membership; list → dictionary for key lookup. One line, and the complexity drops a whole step.

State the time complexity of each fragment, as a function of n = len(agenda), and justify the answer in one sentence.

This function checks which tasks from a list of new jobs already exist in the agenda. State its complexity, rewrite it so it is O(n + m) (with m being the number of new jobs) and state how much extra memory the new version uses.

Write a function that measures with time.perf_counter() how long x in my_list takes against x in my_set when looking for an element that is not there, for n = 10,000 and n = 100,000. Predict before running what will happen to each time when n is multiplied by ten, and check whether you were right.

Solution 1.

The (b) is the most instructive case: there are no two indented loops in sight, but the comprehension inside is the inner loop. The correct version builds the set of titles just once, outside the loop, and comes out O(n).

Solution 2.

The original version is O(n × m): for every job it sweeps the whole agenda. The rewrite replaces the inner loop with a set:

Building the set costs O(n) and the comprehension O(m), so the total is O(n + m). With 200,000 tasks and 100 jobs, you go from 20 million comparisons to 200,100 operations: about a hundred times fewer. The cost is O(n) of extra memory —the set of titles—, and it is the time-memory trade-off in its cleanest form: one extra line, one step of complexity less.

Solution 3.

The prediction follows straight from the table in section 10: in over a list is O(n), so multiplying n by ten multiplies the time by ten; over a set it is O(1), so it does not change. Running it you will see exactly that: the list goes from a few tenths of a millisecond to a few milliseconds, while the set stays nailed to the order of a millionth of a second, whatever its size. Looking for the absent element is deliberate: it is the list's worst case, forcing a full sweep, and for the set nothing changes. Keep this experiment: it is the practical demonstration of the whole module in twenty lines.

Efficiency is not measured in seconds because seconds depend on the machine, on the language and on luck. It is described by counting elementary operations as a function of n and keeping how they grow: that is Big-O notation, an upper bound in which multiplicative constants and lower-order terms are ignored, so that 3n + 5 is O(n) and n² + 500n is O(n²). The catalogue fits on one line —O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)— and every one of them has its example in this course, from a dictionary access to naive Fibonacci. To analyse code, three rules are enough: individual statements are O(1), sequential loops add up and nested ones multiply, and the dominant term rules. By convention we talk about the worst case, because it is the only one that offers guarantees. And alongside time there is space complexity, with its time-memory trade-off: memoisation and inverted indexes spend O(n) of memory to bring the time down a whole step. The cost table for lists, dictionaries and sets —with in at O(n) against O(1), and the insert(0, x) and pop(0) that are O(n) without looking like it— is the cheat sheet you will use daily. But the most important conclusion is the opposite one: while n is small, clarity rules; measure before you touch and optimise only what the measurement points at.

That closes module 6, and with it the black boxes we had been dragging along. You know how to search: linearly with an early exit, binarily by discarding halves over sorted data and by key thanks to the hash table, as well as preparing inverted indexes when a query repeats. You know how to sort: selection, insertion and bubble with its sentinel, the difference between stable and unstable, the divide strategy behind mergesort and quicksort, and the professional use of sorted/.sort() with key, reverse and tuples for several criteria. You know how to use recursion with its base case and its recursive case, to recognise when it wins —tree-shaped data, algorithms that divide— and to fix its repeated work with memoisation. And now you know how to say how much all of that costs. EasyTask has reached v0.14: it searches, sorts by two criteria, hands out tomorrow's plan and adds up projects broken down to any depth.

And yet, look at what holds all of that up: a list of dictionaries. Nothing stops one dictionary from missing the completed key, another from having priority written as "High", or a third from dragging along an invented field nobody else understands; the program will not protest until it blows up with a KeyError halfway through the listing. And the functions that operate on tasks —show_card, total_days, sort_key— are scattered around the file, separated from the data they manipulate, with nothing saying that they form a set. In From data to objects: classes and instances module 7 begins, where data and behaviour stop travelling separately: you will learn to define what exactly a task is, guarantee that they are all born complete and keep the operations that belong to them right next to them.