Axiom

AxiomMaths

Big O notation

Why an algorithm's cost is written the way it is, and what each piece of the notation quietly hides.

Read in order

  1. What a cost is made ofCost gets written as a sum of pieces, and the pieces have names. What is a piece, what does its name actually describe, and why is cutting a cost up this way the thing that lets you compare two programs at all?
  2. What we agree to throw awayIf we agree to discard every constant factor and every lower-order term (a piece that grows more slowly than the fastest piece in the sum), what is left that still tells the truth about an algorithm, and what have we deliberately made ourselves blind to?
  3. Summing a loopEveryone calls a nested loop quadratic before anyone counts it. If we actually count how many times the inner line runs, what number do we get, and why is the honest answer only half of n squared?
  4. Logarithms, and why the base stops matteringIf repeatedly halving a range until one item is left is the whole of what a logarithm counts, why does it make almost no difference whether you halve the range, cut it in three, or cut it in ten?
  5. What O(f) actually isWe write T(n) = O(n^2) with an equals sign, yet you cannot swap the two sides and the right side is not a single number. What kind of object is O(n^2), such that a cost can be said to equal it?
  6. Upper, lower, and tightO(f) only promises a cost grows no faster than f. What says it grows no slower, what says it grows at exactly the rate of f, and why is none of that the same question as best case versus worst case?
  7. Recurrence relationsA recursive algorithm's cost is written in terms of its own cost on smaller inputs, so the cost equation refers to itself. How do you turn that self-reference into one plain cost, and why does splitting the work in half and combining the halves give n times log n?
  8. ExpectationThe average case averages a cost over inputs, but an average has to know how much each input counts. What is that average actually taken over, and why is the weighting a choice you make rather than a fact of the problem?
  9. Best, worst, and averageTwo earlier lessons said the growth bounds and the choice of input are different axes, and one built the average. So what are the three cases, how does each combine with an upper, lower, or tight bound, and why does asking for "the complexity" of an algorithm have no single answer?
  10. When the constants come backThe whole arc agreed to discard constant factors because they stop mattering eventually. Real programs run at a finite size. So at what size does the discarded constant decide which algorithm is actually faster, and why does real merge sort hand small lists to a slower-looking method?
  11. Amortised analysisAdding an item to a growing array is usually cheap, but now and then the array is full and every item must be copied to a bigger block, which costs n. So how can adding an item be called constant time when some additions cost n, and what does it mean to average over a sequence of operations rather than over inputs?
  12. The machine modelThe whole arc counted steps and treated every step as costing the same, but never said what one step is. What is the model that makes "one step" well defined, and what does treating all steps as equal quietly assume that a real machine breaks?
  13. The doubling testEach growth shape answers a doubled input in its own way: constant stays, linear doubles, quadratic quadruples. Run that backwards, measuring how the cost responds when you double the input and reading off the shape you were not told, and you have a diagnostic. How does it work and where does it mislead?
  14. Proof by inductionThe pairing picture showed that one plus two up to n equals n times n plus one over two, but only for the sizes small enough to draw. A picture of four rows is not a proof for every n. How do you close the gap between "true for the cases I checked" and "true for every n" without checking infinitely many?
  15. Limits and dominanceThe arc kept saying one shape eventually grows faster than another, a logarithm slower than any straight line, a square faster than any line. What does "eventually outgrows" mean exactly, and how do you establish it for certain instead of trusting a handful of values?
  16. Sets and membershipThe O(f) lesson called O of n squared a set of functions and wrote that a cost belongs to it, leaning on the words set and belongs as if they were obvious. What is a set, what is it for a thing to belong to one, and why do the growth classes nest inside each other?
  17. Lower bound proofsA lower bound on one algorithm says that algorithm cannot do better. A lower bound on a problem says no algorithm can, including ones nobody has written yet. How do you prove the second kind, that every possible method must do at least a certain amount of work?