Measuring and Trade-Offs

Prove Big-O with a stopwatch, then meet its other half: memory.

Updated

Measure It

  1. Is It Really Slow? Measure Your Own Code (Apprentice): Time real code with your language's stopwatch at growing sizes, run it several times and keep the fastest, then read the growth rate from how the times change when the data doubles.
  2. Answer It in One Step: Trading Memory for Time (Apprentice): Answer "how long are the first few songs?" in one step instead of a loop, by spending a little memory on running totals, and measure both sides of that trade in Big-O: time complexity and space complexity.

In Your Textbook

  1. In Your Textbook: Big-O, Big-Θ and Big-Ω (Journeyman): What a Data Structures textbook means by Big-O, Big-Theta and Big-Omega, how to read each symbol aloud, and its formal definition of Big-O in everyday words, checked with a little code.

Exercise: Race Two Solutions

  1. Exercise: Race Two Solutions (Apprentice): Product needs to know, with numbers, how the repeats report grows and how long it will take for 64,000 songs: build a stopwatch in your language, race two finished solutions at four sizes, keep the fastest of five runs, name each growth rate from your measurements, and predict a time you haven't measured.