Counting Steps
Measuring speed fairly.
How do you measure how fast an algorithm is? A stopwatch isn't fair. A fast laptop beats a slow one, with the same code. So instead, we count the steps an algorithm takes, and ask how that number grows as the input grows.

- A stopwatch isn't fair
- Count the steps instead
- How does it grow?
Counting steps in a loop
Here we count the steps needed to add up a list. Each pass of the loop is one step. We try lists of ten, a hundred, and a thousand items. Run it. Ten times more items means ten times more steps. The steps grow in a straight line with the input.
def total(numbers):
steps = 0
result = 0
for n in numbers:
result += n
steps += 1
return steps
for size in [10, 100, 1000]:
print(size, "items ->", total(range(size)), "steps")10 items -> 10 steps 100 items -> 100 steps 1000 items -> 1000 steps
What we care about
When we count steps, we care about the big picture, not the exact number. Ten steps or twelve doesn't matter. What matters is the shape of the growth, when the input becomes a million. And we usually think about the worst case, the slowest the algorithm can possibly be.
Summary
We measure algorithms by counting steps, and watching how the count grows with the input. Next, the language for describing that growth. Big O.
Key takeaways- Steps, not seconds
- Watch the growth
- Think worst case