← Lectures
Back

1 / 8

Next

Slide 1 of 8: What the notation actually says

Arrow keys move through the slides while these controls have focus.

The theatre is not shown, because your system asks for reduced motion. The lecture itself is below, in full.

Lecture · 8 slides

Big-O, and what it deliberately ignores

Big-O notation is taught as a way of saying how fast an algorithm is, which is not what it does, and the gap between those two things is responsible for a great deal of confidently wrong engineering.

What it actually describes is how the cost of an algorithm grows as its input grows, in the limit, with every constant factor discarded. Each of those qualifications is doing real work. "In the limit" means the answer may be useless at the sizes you have. "Constant factor discarded" means an algorithm that is a hundred times slower can have the same notation. And "cost" is usually a count of abstract operations that bears an increasingly loose relationship to time on a machine with a cache.

None of this makes the notation bad. It makes it a specific tool with a specific purpose, which is to tell you which algorithms will still work when the data gets much larger than it is today. That is an enormously valuable thing to know and it is almost the only thing big-O will tell you. This lecture is about what it discards, and about when what it discards is the part that matters.

AssumesYou have seen O(n) and O(n log n) written down and can read a loop.

  1. Slide 1

    What the notation actually says

    O(f(n)) is a claim about growth, not about speed: beyond some input size, the cost stays below some constant multiple of f(n).

    n      n²
1000   1,000,000
2000   4,000,000
    plaintext

    Double the input to a quadratic algorithm and the work quadruples. That is the entire content of the statement, and it is why the notation is written without constants — they do not affect the shape of that relationship, only where it starts.

    The consequence people find hardest is that O(n) and O(1000n) are the same class. So are O(n²) and O(n²/100). The notation is deliberately blind to any factor that does not change with n, because those factors depend on your machine, your language and your compiler, and the whole point is to say something that survives all three.

  2. Slide 2

    The limit is not where you live

    The phrase "for sufficiently large n" is doing an enormous amount of quiet work, and sufficiently large is often larger than any input you will ever have.

    Insertion sort is O(n²) and quicksort is O(n log n), which sounds decisive. For arrays of fewer than about twenty elements insertion sort is reliably faster, because its constant factor is tiny and it touches memory in a straight line. This is not a curiosity. It is why almost every production sort — including the ones in your standard library — is a hybrid that switches to insertion sort for small partitions, and the quicksort hanging in the Gallery of Methods is the teaching version rather than the shipping one.

    The lesson generalises. Asymptotic notation answers "what happens when this grows", and if the thing is never going to grow, it has answered a question you did not ask.

  3. Slide 3

    The constant hides the machine

    The discarded constant is where all the hardware went, and on modern processors it is worth a factor of ten.

    array of 1M ints, summed
sequential:  ~1 ms
random order: ~15 ms
    plaintext

    Both are O(n). Both perform the same number of additions. The difference is that one walks memory in order, so the prefetcher has the next cache line ready before it is asked, and the other does not. A cache miss costs a couple of hundred cycles, an addition costs one, and the notation cannot see the difference between them because neither depends on n.

    This is why a linked list loses to an array for almost every real workload despite identical complexity for traversal, and why a linear scan of a small contiguous array often beats a hash lookup that is O(1). The theory has not been refuted. It has been asked a question about constants and has, correctly, declined to answer.

  4. Slide 4

    Which case are you quoting

    Every algorithm has a best, a worst and an average, and quoting one without saying which is the commonest way to mislead people accidentally.

    Quicksort is O(n log n) on average and O(n²) in the worst case, when the pivot is consistently the smallest or largest element. That worst case is not theoretical: it is what a sorted array does to a naive implementation, and sorted arrays are extremely common in practice. The fix is to choose the pivot randomly, which is the same trick the Fisher-Yates shuffle in the Gallery of Methods exists to do correctly.

    Hash tables are the sharper example. O(1) lookup is the average, and the worst case is O(n) when every key collides. For most of a career this never matters, and then somebody discovers that your web framework hashes query parameters and sends you a request with ten thousand colliding keys.

  5. Slide 5

    Amortised is a promise about totals

    A third kind of claim looks like a lie until you understand what is being averaged, and it is what makes a dynamic array possible.

    Appending to a growable array is O(1) amortised. Most appends write one slot and stop; occasionally the array is full and everything must be copied to a larger block, which is O(n). Averaged over any long sequence of appends the cost per operation is constant, because doubling the capacity means the expensive copies get exponentially rarer.

    The distinction from average-case is worth keeping. Average-case is a statement about typical inputs and can be defeated by an unlucky one. Amortised is a statement about a sequence of operations and cannot — the total is bounded regardless of order. Which also means it is the wrong guarantee for a system where one slow operation is unacceptable, because the expensive copy still happens, just rarely. A real-time audio thread does not care that the average was fine.

  6. Slide 6

    The cases where it is decisive

    Having spent five slides on the limits, it is worth being clear that when this notation matters, it matters more than anything else you can do.

    The difference between O(n²) and O(n log n) at a million elements is roughly fifty thousand fold. No amount of optimising, no faster language, no additional hardware closes that. This is the situation the notation was invented for, and it is why the answer to "my program got slow when the data grew" is almost never a profiler and almost always a data structure.

    Binary search, hanging a few frames from the quicksort, is the cleanest case in the museum. Twenty comparisons to find one item among a million, because each step halves what remains. There is no way to make a linear scan competitive with that, and no constant factor large enough to matter.

  7. Slide 7

    Reading the shape of the code

    The practical skill is not computing complexity formally. It is looking at a function and seeing which class it is in, which is usually visible.

    Nested loops over the same collection are quadratic. Halving the problem each step gives a logarithm. A loop containing a lookup that is itself a scan is the commonest accidental quadratic in real code, and it hides well because neither piece looks expensive. Recursion that splits in two and does linear work per level is n log n, which is where the sorting bound comes from.

    The one worth watching for is the accidental one. A list membership test inside a loop over the same list is O(n²) written as two innocuous lines, and it will be fine on your test data and fatal on production data. Most real performance disasters are this, rather than anything anybody chose.

  8. Slide 8

    The honest summary

    Use big-O for the question it answers: will this still work when the input is ten or a hundred times bigger? For that question nothing else comes close.

    Do not use it to choose between two implementations of the same class, or to predict how long anything will take, or to justify a data structure without measuring. The constant factors it discards are where the hardware lives, and on current hardware they are worth an order of magnitude — enough that "which is faster" and "which has better complexity" are genuinely different questions with genuinely different answers.

    And when they disagree, measure. The notation is a statement about mathematics that happens to be useful about machines, and the machine is the thing your program is going to run on.

Works in the collection

The arguments above are hanging on the walls of the museum, in one form or another. These are the ones worth looking at next.

The rest of the programme

  1. Compiled, interpreted, and the space betweenA distinction that stopped describing anything decades ago, why it persists, and what is actually different about the machinery underneath.
  2. What a compiler actually doesFour jobs in a row, each mechanical, none magic: text to tokens, tokens to a tree, a tree to a judgement, and a judgement to instructions.
  3. Functional programming and object orientationTwo ways of arranging a program, what each one genuinely makes easy, and the trade-off underneath the argument that neither side can escape.
  4. The principles of object orientationEncapsulation, inheritance, polymorphism and SOLID, one at a time: what each actually claims, which held up, and which its own community abandoned.
  5. Types: what they can and cannot proveA type checker proves one thing about every possible run of your program. Knowing which proposition explains both the enthusiasm and the disappointment.
  6. Null, and the mistake its inventor apologised forTony Hoare called it his billion-dollar mistake. What was actually wrong with it, what the alternatives cost, and why the fix took forty years to arrive.
  7. What abstraction costsAbstraction is sold as free and is not. What you buy, what you pay, and how to tell before writing it which of the two is larger.
  8. Immutability, and what it is not free ofValues that never change buy sharing, comparison and time travel. They are not free, and it is worth knowing where they are expensive before you commit.
  9. Recursion, and why it feels like cheatingA function that calls itself looks like an unpaid debt. What makes it terminate, what it costs on the stack, and why some problems resist any other shape.
  10. What regular expressions cannot matchThere is a precise boundary around what a regex can recognise. It explains the famous refusal to parse HTML, and why some patterns run forever.
  11. Concurrency is not parallelismOne is a way of structuring a program, the other a way of executing it. Keeping them apart explains why async helps a web server and threads often do not.
  12. Errors: exceptions, values, and what each hidesThrowing makes the happy path readable and the failure paths invisible. Returning errors as values does the opposite. Neither side has won.
  13. Why programs are hard to changeSoftware is called soft because it can be edited. Why editing gets harder every year, what the mechanism is, and which of the usual remedies work.

← All lecturesAtrium