Comparing two algorithms on paper

Why this matters

Many problems have more than one solution. A beginner usually writes the first idea that works, and that is a good start. Before you pick one, you need a way to compare them that does not depend on your computer. This lesson shows how to count the work each solution does, write the counts in a table, and read the table.

The method is simple: pick one problem, write two solutions, count the steps each one takes for a few input sizes, and compare the numbers. You do not need to time the programs. Timing depends on the machine, the language and the load on the computer at that moment. A count of steps stays the same on every machine.

The loops you met in earlier lessons are the main source of work in most programs, so the counts in this lesson mostly come from loops. The lesson on flowcharts for loops and early exits draws loops as boxes, and the next lesson in this module shows one flowchart written in three languages.

One problem, two solutions

The problem is this. Given a whole number n, find the total of all the numbers from 1 to n. For example, with n equal to 4 the total is 1 + 2 + 3 + 4, which is 10.

The number n is the input size. It is the amount of data the solution has to handle. A solution that handles 4 numbers and a solution that handles 1,000,000 numbers can have very different costs, and the input size is what lets us compare them fairly.

Here are two solutions.

Solution A adds the numbers one at a time with a loop. It goes through 1, then 2, then 3, and so on up to n, and keeps a running total.

Solution B uses a formula. A formula is a fixed calculation that gives the answer straight from n. For this problem the formula is n times n + 1, divided by 2.

Both solutions give the same answer. The question is how much work each one does to get there.

What counts as a step

A step is one unit of work that the solution does. For this lesson, we count one step as one arithmetic operation: one addition, one multiplication or one division. Each of these takes the computer a small, fixed amount of effort.

We are counting only additions for Solution A, and only the three operations in Solution B. The loop also checks whether it should keep going, and that check costs about as much as the addition. Leaving the checks out does not change the comparison, because the number of checks grows at the same rate as the number of additions. We will keep the count simple so that you can do it on paper.

The rule is that you must use the same definition of a step for both solutions. If you count additions in one and checks in the other, the comparison is wrong.

Solution A: the loop

Here is Solution A in Python. Python is a programming language that reads close to plain English, and it is a good choice for this kind of counting.

def sum_with_loop(n):
    total = 0
    additions = 0
    for number in range(1, n + 1):
        total = total + number
        additions = additions + 1
    return total, additions

The function sum_with_loop takes n and returns two values: the total, and how many additions it made. The additions variable is there only for counting. It does not change the answer.

Here is the work for n equal to 4, written out by hand as a trace table. A trace table is a list of each step with the values after it. You fill it in with a pencil, one row per loop round.

The loop ran 4 times. It made 4 additions. The total is 10.

The number of additions grows with n. If n is 100, the loop makes 100 additions. If n is 1,000,000, it makes 1,000,000 additions. Each time n gets bigger by a factor of 10, the work gets bigger by the same factor of 10.

Solution B: the formula

To see where the formula comes from, pair the numbers from both ends. Take n equal to 10. Add the first number to the last, then the second to the second last, and so on.

• 1 + 10 = 11
• 2 + 9 = 11
• 3 + 8 = 11
• 4 + 7 = 11
• 5 + 6 = 11

There are 5 pairs and each one adds to 11. So the total is 5 times 11, which is 55. The 5 is half of 10, and the 11 is 10 + 1. For any even n the same pattern holds: there are n divided by 2 pairs, and each pair adds to n + 1. That gives the formula n times n + 1, divided by 2.

Here is Solution B in Python:

def sum_with_formula(n):
    total = n * (n + 1) // 2
    operations = 3  # one add, one multiply, one divide
    return total, operations

The line total = n * (n + 1) // 2 does three operations: an addition inside the brackets, a multiplication, and a division. The // symbol means integer division. It divides and drops any fraction. For this formula the result is always a whole number, so dropping a fraction never changes the answer.

The number of operations is 3 for every value of n. If n is 4, it is 3. If n is 1,000,000, it is still 3. The work does not depend on n.

Counting on paper

Before you write any code, you can count the work by hand. Take n equal to 4.

For Solution A, write one tally mark for each addition. The trace table above had four rows with an addition in each row, so the tally is four marks.

For Solution B, write the three operations: one addition (4 + 1 = 5), one multiplication (4 times 5 = 20), and one division (20 divided by 2 = 10). The tally is three.

So for n equal to 4, Solution A does 4 steps and Solution B does 3 steps. At this size the two solutions cost almost the same. The difference matters when n gets large, and the next section shows that.

Running the counts

The script below runs both solutions for many values of n, checks that they agree, and prints a cost table. A cost table is a table that puts the input size in one column and the number of steps for each solution in the other columns.

def sum_with_loop(n):
    total = 0
    additions = 0
    for number in range(1, n + 1):
        total = total + number
        additions = additions + 1
    return total, additions
 
 
def sum_with_formula(n):
    total = n * (n + 1) // 2
    operations = 3  # one add, one multiply, one divide
    return total, operations
 
 
if __name__ == "__main__":
    print("Check that both solutions give the same answer for n = 1 to 1000")
    mismatches = 0
    for n in range(1, 1001):
        loop_total, _ = sum_with_loop(n)
        formula_total, _ = sum_with_formula(n)
        if loop_total != formula_total:
            mismatches = mismatches + 1
    print("mismatches:", mismatches)
 
    print()
    print("Problem 1: sum of 1 to n")
    print(f"{'n':>10} {'loop additions':>15} {'formula operations':>19} {'answer':>20}")
    for n in [10, 100, 1000, 1000000]:
        total, additions = sum_with_loop(n)
        _, operations = sum_with_formula(n)
        print(f"{n:>10} {additions:>15} {operations:>19} {total:>20}")

Running it with python3 sum_compare.py prints this:

Check that both solutions give the same answer for n = 1 to 1000
mismatches: 0
 
Problem 1: sum of 1 to n
         n  loop additions  formula operations               answer
        10              10                   3                   55
       100             100                   3                 5050
      1000            1000                   3               500500
   1000000         1000000                   3         500000500000

The first line of output shows that the two solutions agree for every n from 1 to 1000. The table shows the cost. The loop cost grows one step for every step in n. The formula cost stays at 3.

Here is the same comparison written as a cost table you can copy into your notes:

Reading the table

Read the table column by column. The loop column goes up by the same amount that n goes up. Each time n grows by 10 times, the number of steps also grows 10 times. The formula column does not move.

Next, read it row by row. At n equal to 10 the difference is 10 steps against 3. At n equal to 1,000,000 the difference is one million steps against 3. The table tells you that for large inputs the formula does far less work.

A table like this is useful even if you never write code, because it answers a question that often comes up: which solution will still be fast enough when the input gets big? Write the counts, look at the largest row, and decide.

Be careful with what the table does not say. It does not say how many seconds each solution takes. Each addition takes a different amount of real time on a real machine, and the loop also has overhead that we did not count. The table says how the work grows, not how long it takes.

A harder problem: the sum of the even numbers

Now a problem where the loop does more checking than adding. The problem is to find the total of the even numbers from 1 to n. For n equal to 10 the even numbers are 2, 4, 6, 8 and 10, and their total is 30.

Here is a loop solution. It checks every number from 1 to n, and it adds only the even ones.

def sum_evens_with_loop(n):
    total = 0
    checks = 0
    additions = 0
    for number in range(1, n + 1):
        checks = checks + 1
        if number % 2 == 0:
            total = total + number
            additions = additions + 1
    return total, checks, additions

The % symbol is the remainder operator. number % 2 gives 0 when the number is even and 1 when it is odd. So number % 2 == 0 is true for even numbers.

For n equal to 10 the loop checks 10 numbers and makes 5 additions. The checks grow with n, and the additions grow with half of n. Both are still linear, which means they grow in a straight line with n.

The formula solution uses the fact that the first k even numbers add to k times k + 1. Here k is the count of even numbers up to n, which is n divided by 2, with any fraction dropped.

def sum_evens_with_formula(n):
    k = n // 2
    total = k * (k + 1)
    operations = 3  # one divide, one add, one multiply
    return total, operations

Check it for n equal to 10. The count of even numbers k is 5. Then k times k + 1 is 5 times 6, which is 30. That matches the direct total.

Here is the cost table for this problem:

The loop does twice as many checks as additions, because half the numbers are odd and skipped. The count of checks is the one that grows with n. The formula still does three operations no matter how large n is.

Checking the two solutions against each other for every n from 1 to 1000 finds no mismatch for this problem. You should always check a formula this way before you rely on it. A formula that is right for n equal to 10 can still be wrong for other values.

Which solution to pick

On paper the formula is always better, because it does 3 steps. In a real project the choice is less simple, and the cost table helps you think about it.

Suppose you are writing a small program for a class exercise where n is never more than 20. Both solutions take a few steps. The loop is easier to read for a beginner, and it is easy to change if the problem changes. Choosing the loop costs you nothing here.

Suppose instead that a program has to add numbers up to a billion for every user who opens a page. A loop that makes a billion additions would take far longer than the formula, and the page would feel slow. The table tells you that the formula is the right choice in that case.

The lesson is that the table makes the cost visible before you write the code. You then decide with the input size in mind, not with a hunch.

Common mistakes

Counting for different inputs. A common error is to count steps for n equal to 10 for one solution and n equal to 100 for the other. The two counts then cannot be compared. Use the same n values in every row of the table for both solutions.

Counting different things. If one solution counts additions and the other counts every line of code, the table is wrong. Choose one definition of a step and use it for both solutions. Write the definition at the top of your table so you remember it.

Using time instead of steps. Some beginners run each program with a stopwatch and treat the time as the cost. Time depends on the machine. Two people running the same code on different computers will see different numbers. Steps do not change from one machine to the next.

Writing a formula that is almost right. For this problem a formula that looks reasonable is n times n - 1, divided by 2. It gives the wrong answer. For n equal to 10 it returns 45, but the correct answer is 55. If you run the code for a few small values and compare with the loop, you find the mistake at once. Always test a formula against the loop before you trust it.

Forgetting that the loop test costs something. When you count only additions, you leave out the loop checks. That is acceptable here because both kinds of work grow at the same rate. But if you count only one kind of work for one solution and forget the other, you can get a misleading table. Say in your notes what you left out.

Passing text where a number is needed. This error is not about counting, but it happens when you test the code. If you call sum_with_formula with a string such as "10" instead of the number 10, Python stops with this message:

TypeError: can only concatenate str (not "int") to str

The message means you tried to add a number to text. Convert the input to a number first with int(...).

Practice

Exercise 1. Solution A is the loop for the sum of 1 to n. For n equal to 6, how many additions does it make? How many operations does Solution B make?

Show the answer: Solution A makes 6 additions, one for each number from 1 to 6. Solution B makes 3 operations for any n.

Exercise 2. Use the formula n times n + 1, divided by 2, to find the sum of 1 to 100 without a loop.

Show the answer: 100 times 101 is 10100. Divided by 2 that is 5050.

Exercise 3. A loop for the sum of 1 to n made 50 additions. What is n?

Show the answer: The loop makes one addition for each number, so n is 50.

Exercise 4. Solution X takes 2n + 5 steps. Solution Y takes n times n steps. Fill in a cost table for n equal to 3, 5 and 10. Which solution is cheaper at each size?

Show the answer: For n equal to 3, X takes 11 steps and Y takes 9, so Y is cheaper. For n equal to 5, X takes 15 and Y takes 25, so X is cheaper. For n equal to 10, X takes 25 and Y takes 100, so X is cheaper. Y is cheaper only at the smallest size.

Exercise 5. A student writes total = n * (n - 1) // 2 for the sum of 1 to n. What does it return for n equal to 10, and what should it return? Explain how you would find the mistake with the loop.

Show the answer: It returns 45, because 10 times 9 is 90 and half of that is 45. The correct answer is 55. To find the mistake, run the loop and the formula for n equal to 10 and compare the two results. The loop gives 55, so the formula is wrong.

Summary

• Define a step first, and use the same definition for every solution you compare.
• Count the work for the same input sizes for each solution, and write the counts in a cost table.
• A loop that goes through all n numbers grows in a straight line with n, while a formula with a fixed number of operations does not grow at all.
• Test a formula against a loop for many small inputs before you rely on it.
• Pick the solution using the input size you expect, and write down what the table does not show, such as time on a real machine.