Foundations · Module 2
Measuring cost: Big-O
Count the steps an algorithm takes and how that count grows, so you can compare solutions before writing them.
Choosing a data structure means predicting how fast it will be before you build it. This module gives you the tools: counting the steps an algorithm takes, summarizing how that count grows with Big-O, telling the best, average and worst cases apart, and accounting for memory and the real-world costs Big-O leaves out. Every later module states its costs in these terms.
- 1Counting stepsBefore you can compare two algorithms, you need a way to measure them that doesn't depend on your laptop. Count the basic steps as a function of the input size.12 min
- 2Growth rates and Big-OBig-O keeps only the part of a step count that grows fastest. It tells you how an algorithm scales, and roughly how big an input it can handle in time.14 min
- 3Best, average and worst caseThe same algorithm can take very different numbers of steps on inputs of the same size. Which case you quote decides whether your estimate is a guarantee or a hope.12 min
- 4Space and hidden costsTime is only one bill an algorithm pays. Memory is the other, and both hide in copies, allocations, recursion and constant factors that Big-O leaves out.12 min