P-5.1 Measuring Cost, and What Big-O Hides

Work through these

• Counting operations as a function of input size

  Start by asking how many times the innermost work happens when the input has size n. Nested loops multiply, sequential loops add, and that accounting is the whole technique.

  MIT OpenCourseWare 6.006: Introduction to Algorithms · Course

• The common growth rates, in order, and what each feels like

  Constant, logarithmic, linear, linear times logarithmic, quadratic and exponential is the ladder nearly everything sits on. Knowing where a rate lands tells you what input size becomes impossible.

• Worst case, average case and best case are different questions

  Quicksort is quadratic at worst and fast in practice; hash lookup is constant on average and linear at worst. Stating which case you mean is part of stating the result.

• What the notation throws away: constants, small inputs, memory

  Two algorithms with the same growth rate can differ tenfold in real time, and for small inputs the worse rate often wins. Memory use and cache behaviour do not appear in the notation at all.

• Measure two implementations and compare against your prediction

  Time both across a range of input sizes and plot what you get. Where measurement disagrees with the analysis, the disagreement is the interesting finding rather than an embarrassment.