AI Hints
Home›DSA in Python Tutorial›Measuring Speed
DSA in Python · Lesson 4 of 132

Counting Steps

Measuring speed fairly.

⏱ 2 min read▶ Video at 3:26🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Counting Steps
From the video: Counting Steps
  • 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.

steps.pypython
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")
Output
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.

Count stepsnot seconds
Growthas input gets bigger
Big pictureignore small details
Worst caseplan for the slowest

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
Next up: Big O Notation — describing growth