Basis Lab

Making it fast enough

Predict how the time and the memory a piece of work needs grow as its input grows, well enough to know which of two approaches is still standing at a million rows, and to tell a slow algorithm apart from a slow machine

How Long It Takes

Counting the work instead of timing it. How to read the cost of a piece of code off its shape, and why the answer is about growth rather than seconds.

8 lessons, written and corrected before you arrived. Reading them here needs no account. The first reads the whole way through; the others open and then stop, because a page nobody owns cannot tell who is reading it. Starting the course gives you your own copy, where every idea has problems standing under it and you can ask about any sentence.

Start reading

This is course 1 of 8 in a reading track: tell in advance which approach survives a million rows. The track is an order, not a gate, and the rest of it is on one page.

  1. 01Counting Steps, Not SecondsA stopwatch measures one machine on one input. Counting the operations a piece of work performs measures the work itself, and that number is the one that predicts next year.
  2. 02The Shape of the Curveopening onlyAlmost all work falls into a handful of growth shapes. Knowing them in order, and knowing what each does when the input doubles, is most of the practical value of the subject.
  3. 03Why the Constants Get Droppedopening onlyThrowing away constant factors and smaller terms is what makes the comparison portable, and it is also what makes it occasionally wrong. Both halves of that are worth holding.
  4. 04Reading the Cost Off the Workopening onlyThree patterns cover most of it: work done in sequence, work nested inside work, and work that halves what is left. Recognising them turns analysis into reading.
  5. 05Best Case, Worst Case, and the One You Getopening onlyThe same procedure has three costs depending on what it is handed. Which of the three to plan around is a question about the situation, not about the code.
  6. 06Space Is a Cost As Wellopening onlyMemory grows with the input too, it runs out more abruptly than time does, and it can be traded against time deliberately in both directions.
  7. 07Occasionally Expensive, Usually Freeopening onlySome operations are almost always instant and occasionally enormous. Averaging the enormous step over the cheap ones around it is the honest accounting, and it is why a growing list stays cheap.
  8. 08When the Analysis Liesopening onlyThree situations where the growth comparison confidently recommends the slower option: small inputs, memory behaviour, and constants nobody counted. All three are common.