Comparing algorithms

Time and space efficiency as functions of the size of the problem; linear, polynomial, exponential and logarithmic functions; permutations and n!.

A5.1Algorithms and complexityA level25 min

At GCSE (F5.9) you compared bubble sort and merge sort by counting their comparisons on one list. At A level you compare algorithms in general: not "how long did it take on this list" but "how does the work grow as the problem gets bigger". This lesson sets up the ideas and the maths; the next one turns them into Big O notation.

Why not use a stopwatch?

Timing a program tells you about one run, on one computer, in one language, with one set of data and whatever else the machine was doing at the time. Run it on the robot's processor and the laptop's, and you get two different answers for the same algorithm.

So algorithms are compared by counting basic operations (a comparison, an assignment, a swap, a visit to a vertex) and writing the count as a function of the size of the problem, called n. For a search, n is the number of items; for a route planner, the number of waypoints.

The size of the problem is the key issue. Almost any algorithm is fast when n is 10. What matters is what happens when n is 10,000, or a million.

Time and space

An algorithm can be efficient in two ways:

• time efficiency: how the number of operations grows with n;
• space efficiency: how much extra memory it needs as n grows, beyond the input itself.

The two often pull against each other. Here are two ways to check whether a list of marker IDs has a repeat:

def repeat_by_pairs(ids):
    """Compare every pair. No extra memory, but many comparisons."""
    checks = 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            checks = checks + 1
            if ids[i] == ids[j]:
                return True, checks
    return False, checks

def repeat_by_set(ids):
    """Remember every ID seen. One check each, but a set that grows to n items."""
    seen = set()
    checks = 0
    for tag in ids:
        checks = checks + 1
        if tag in seen:
            return True, checks
        seen.add(tag)
    return False, checks

for n in [10, 100, 500]:
    ids = list(range(n))                    # no repeats: the worst case for both
    print(n, "IDs: pairs", repeat_by_pairs(ids)[1], "checks, set", repeat_by_set(ids)[1], "checks")

Run this in the simulator

For 500 IDs the pairs method makes 124,750 comparisons and the set method 500, but the set method holds up to 500 extra items in memory. On a microcontroller with very little RAM, the slower method might be the right choice. Neither is "best": it depends on n and on the machine.

The maths: four kinds of function

To describe growth you need four families of function. Each is shown with n as the input.

A polynomial function has n raised to a fixed power: n², n³, 5n² + 3n. An exponential function has n as the power: 2ⁿ, 3ⁿ. That difference is enormous. Adding one waypoint to an exponential algorithm doubles its work; adding one to a quadratic algorithm barely changes it.

A logarithm undoes a power: log₂ n = x means 2ˣ = n. So log₂ 1024 = 10. A useful way to read it: log₂ n is roughly how many times you can halve n before you reach 1. That is why halving algorithms, like binary search, are logarithmic. AQA's specification writes its example as log₁₀ n; the base does not change the shape, because log₂ n = log₁₀ n ÷ log₁₀ 2, which is only a constant multiple.

On the graph, the order from slowest-growing to fastest is: constant, logarithmic, linear, n log n, polynomial, exponential. For small n the curves cross and tangle; for large n the order never changes.

Permutations

A permutation is one ordering of a set of objects. The robot has to visit 4 checkpoints, A, B, C and D, in some order. How many orders are there?

• 4 choices for the first checkpoint,
• then 3 left for the second,
• then 2, then 1.

That is 4 × 3 × 2 × 1 = 24. In general, the number of permutations of n distinct objects is n factorial, written n!:

n! = n × (n - 1) × (n - 2) × ... × 2 × 1

from itertools import permutations

checkpoints = ["A", "B", "C", "D"]
orders = list(permutations(checkpoints))
print(len(orders), "orders, starting", orders[:3])

total = 1
for k in range(1, 11):
    total = total * k
    print(k, "checkpoints:", total, "orders")

Run this in the simulator

Factorial grows even faster than 2ⁿ: 10! is 3,628,800 but 2¹⁰ is only 1,024. An algorithm that tries every order of n checkpoints to find the shortest tour is doing n! work, and it becomes hopeless at around 15 to 20 checkpoints however fast the computer is. You will see in A5.7 that finding the shortest route between two points does not need anything like this.

Task: the growth table

Print a table of how four functions grow. For each n in 4, 8, 16, 32 and 64, print one line in exactly this form:

n=8 log2=3 square=64 exponential=256

where log2 is log₂ n (a whole number here, because every n is a power of 2), square is n² and exponential is 2ⁿ. Work out log2 by counting how many times n can be halved (with // 2) before it reaches 1, not with the math module.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

n = 8
print("n=" + str(n))

Task: brute force routes

Write a function orders(n) that takes a whole number n (1 or more) and returns n!, using a loop (not math.factorial). Then print three lines:

• 6 checkpoints: 720 orders
• 10 checkpoints: <10!> orders
• 20 checkpoints: <years> years

For the last line, suppose a computer checks one billion (10⁹) orders every second. Work out how long it would take to check all 20! orders, in years of 365 days, and print the whole number of years, rounded down.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def orders(n):
    return n

Challenges

1. From which n onwards is 2ⁿ always bigger than n²? Check your answer with a loop up to n = 30.
2. The robot's memory holds 64,000 IDs. Which duplicate check from this lesson could it run on 50,000 IDs, and which could it not? Explain.
3. How many different orders are there for 5 checkpoints if the robot must always start at A?