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

• Some algorithms grow slowly: double the input, do about double the work.
• Some algorithms grow fast: a little more input means a huge jump in work.
• "Reasonable" run time grows slowly enough to finish; "unreasonable" blows up.

Input size:      10        20        40
Search a list:   10        20        40        (slow growth - reasonable)
Try all orders:  3,628,800 ...       a number with 48 digits   (explodes!)

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 fast algorithm.
• The only methods try a huge number of possibilities — too slow for big input.
• For these, we often accept a good-enough answer instead of the perfect one.

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.

Fast            : finishes quickly, even for big input
Slow but doable : finishes, but may take a very long time
Undecidable     : no algorithm can solve it for every input

Key ideas to remember

• Efficiency is about how work grows with input size.
• Slow-growing algorithms scale to big inputs; fast-growing ones do not.
• Some problems are unreasonable to solve exactly, and some are undecidable.

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". Press Check answer.