How fast is an algorithm?

What you'll learn

Count a program's steps instead of timing it
See how the number of steps grows when the data gets twice as big
Replace a slow algorithm with a fast one

Counting steps instead of timing

How fast a program is also depends on the computer. A new laptop is faster than an old one. That’s why computer scientists prefer to count steps. The question is: how many steps does an algorithm need when the data gets bigger?

In the Python lesson “Algorithms” you already saw that binary search manages with 20 steps where linear search needs a million. Here we look more closely at how the steps grow.

One loop: twice the data, twice the steps

To find the largest number in a list, you have to look at every number once. With twice as many numbers, it’s twice as many steps. That’s called linear:

def largest(items):
    steps = 0
    best = items[0]
    for number in items:
        steps = steps + 1
        if number > best:
            best = number
    return steps


for n in [10, 20, 40, 80]:
    print(f"{n:3} numbers → {largest(list(range(n))):3} steps")

Two nested loops: four times the steps

In a class, everybody should shake hands with everybody else once. With n people that’s n · (n − 1) / 2 handshakes. If you double the class, there are almost four times as many. That’s called quadratic:

def handshakes(n):
    steps = 0
    for a in range(n):
        for b in range(a + 1, n):
            steps = steps + 1
    return steps


for n in [10, 20, 40, 80]:
    print(f"{n:3} people → {handshakes(n):5} handshakes")

With 80 people it’s already 3160. With a million records it would be 500 billion steps – that takes far too long even for a fast computer.

Compared

Data	linear	quadratic	binary search
10	10	45	4
1,000	1,000	499,500	10
1,000,000	1,000,000	≈ 500 billion	20

Computer scientists write O(n), O(n²) and O(log n) for this. The “O” means: this is roughly how the number of steps grows when n gets bigger.

Quick check

How many steps does this program count? Think first, then type.

steps = 0
for a in range(4):
    for b in range(4):
        steps = steps + 1
print(steps)

For the task: a look into a set (value in seen) only costs one step, no matter how big the set is. A look into a list, on the other hand, may have to check every element in the worst case. That’s exactly why the fast way is so fast.

Your task

Your turn

Find out whether a value appears twice in a list – in two ways, and count the comparisons. duplicate_slow(items) compares every pair once (two nested loops, the inner one starts after the outer one). duplicate_fast(items) remembers the values it has already seen in a set and counts every look into the set as one comparison. Both return a pair: (found, comparisons). As soon as a duplicate is found, both stop right away.

def duplicate_slow(items):
    comparisons = 0
    return False, comparisons


def duplicate_fast(items):
    comparisons = 0
    seen = set()
    return False, comparisons


numbers = list(range(1000))
print(duplicate_slow(numbers))
print(duplicate_fast(numbers))

Something to think about
Return (True, comparisons) as soon as two equal values are found – and (False, comparisons) only after the loops.
Which command helps?
The inner loop starts after the outer one: for j in range(i + 1, len(items)) – then you count every pair exactly once.
Per value: comparisons + 1, then if value in seen: … otherwise seen.add(value).

Gap code – fill in the ___

                        def duplicate_slow(items):
    comparisons = 0
    for i in ___:
        for j in ___:
            comparisons = ___
            if ___:
                return ___
    return False, comparisons


def duplicate_fast(items):
    comparisons = 0
    seen = set()
    for value in ___:
        comparisons = ___
        if ___:
            return ___
        seen.add(___)
    return False, comparisons


numbers = list(range(1000))
print(duplicate_slow(numbers))
print(duplicate_fast(numbers))

Solve it without hints to earn a ⭐ on your progress page.

Show solution

Try it yourself first – mistakes teach you the most. Here is one possible solution:

def duplicate_slow(items):
    comparisons = 0
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            comparisons = comparisons + 1
            if items[i] == items[j]:
                return True, comparisons
    return False, comparisons


def duplicate_fast(items):
    comparisons = 0
    seen = set()
    for value in items:
        comparisons = comparisons + 1
        if value in seen:
            return True, comparisons
        seen.add(value)
    return False, comparisons


numbers = list(range(1000))
print(duplicate_slow(numbers))
print(duplicate_fast(numbers))