Algorithmic efficiency

What we'll do

• Two programs can both be correct but take very different time.
• This lesson is about efficiency: how the work grows as the input grows.
• Read and think about the ideas; then a few short tasks let you count the steps yourself.

Counting the work

• We measure an algorithm by how many steps it does, not seconds.
• Steps in seconds depend on the computer; counting steps does not.
• More input usually means more steps. The question is how much more.

Reasonable vs unreasonable run time

• Reasonable time means the number of steps grows as a polynomial, or more slowly: constant, linear, square or cube.
• A single loop is linear. A loop inside a loop is square (n × n). Square grows faster than a line, and it is still reasonable time.
• Unreasonable time means exponential or factorial growth. A little more input makes the work blow up.

Input size:      10          20          40
Search a list:   10          20          40          (linear - reasonable)
Nested loops:    100         400         1,600       (square - still reasonable)
Try all orders:  3,628,800   ...         48 digits   (factorial - unreasonable)

A tiny demo: counting steps

• Below we count the comparisons a linear search makes.
• The count grows in step with the list size — slow, steady growth.
• Try changing the size to see the count follow it.

def count_steps(n):
    steps = 0
    data = list(range(n))
    target = -1            # not in the list, so we scan everything
    for item in data:
        steps = steps + 1
        if item == target:
            break
    return steps

print(count_steps(10))
print(count_steps(20))
print(count_steps(40))

When fast is not enough

• Some problems have no known reasonable-time algorithm.
• An exact method may try every order. That is factorial growth, so it is unreasonable for a large input.
• A heuristic is a shortcut that can give a good-enough answer. It is not guaranteed to be the best one. You do not need to memorise one particular heuristic.

Undecidable problems

• Worse than slow: some problems cannot be solved by any algorithm at all.
• These are called undecidable problems.
• No matter how fast computers get, no program can always give the right answer.

Reasonable   : constant, linear, square or cube growth
Unreasonable : exponential or factorial growth
Undecidable  : no algorithm can solve it for every input

Key ideas to remember

• Efficiency is about how the number of steps grows with input size, not how many seconds one computer takes.
• Polynomial growth or lower is reasonable time. A nested loop (n × n) is still reasonable.
• Exponential or factorial growth is unreasonable. Some problems are also undecidable.

Common mistakes

• Calling a nested loop unreasonable. Square and cube growth are still reasonable time.
• Using formal Big-O notation as the exam rule. Big-O is not tested. The line is polynomial or lower, versus exponential or factorial.

Now you try

• Write small functions that count steps to feel how the work grows.
• Compare a single loop, a nested loop, and "try all orders". The nested loop is still reasonable time. Press Check answer.