Six short lessons for someone who has never studied algorithms: trace a procedure by hand, count its steps, read big-O, write a recursive function, argue that a loop is correct, and prove a claim by induction. Every example is Python and runs on the page.
What you need first
Nothing to install. Every example is Python and runs on this page: press Run under the code. You can also change the code and run it again.
School arithmetic: add, subtract, multiply and divide, compare two whole numbers, and know that 2 × 2 × 2 is 8.
No programming. Every Python word is explained the first time it appears, and lesson 1 starts with a very small program.
Pencil and paper. Tracing by hand is the main skill here, and writing it down is how it is learned.
01
What an algorithm is, and tracing one by hand
Goal After this you can say what an algorithm is, and follow one on paper, writing down every variable after every step.
An algorithm is a list of exact steps that turns an input into an output. A cooking recipe is close, but a recipe says things like "add salt to taste". An algorithm leaves no room for taste. Each step must be so clear that a machine, or a person who does not know the goal, can follow it.
To talk about an algorithm you state three things. The input is what goes in. The output is what must come out. The steps are what happens in between. The input and the output together are called the specification. It says what the algorithm must do, not how. Here the specification is: the input is a list of whole numbers with at least one number in it, and the output is the largest number in the list.
Here is an algorithm for that. Look at the first number and call it the largest so far. Then go through the other numbers one at a time. If a number is bigger than the largest so far, it becomes the new largest so far. When the numbers run out, the largest so far is the answer.
Tracing means playing the computer by hand. You follow the steps exactly, and after every step you write down the current value of every variable. A variable is a name attached to a value. Here the name largest is attached to a number, and that number can change. A trace is usually a table with one row per step. Every later lesson uses tracing. If you can trace an algorithm, you can find out what it does without trusting anyone.
The example below is the same algorithm in Python, the programming language this guide uses. Press Run to watch it work, then read the code from top to bottom. The step-by-step notes explain every line.
New words
algorithm
A list of exact steps that turns an input into an output.
specification
The allowed inputs and the required output. It says what to do, not how.
variable
A name attached to a value. The value can change while the name stays.
trace
Following an algorithm by hand and writing down every variable after every step.
list
A row of values in square brackets, such as [3, 8, 2]. The first item is at position 0.
loop
Steps that repeat. Here they repeat once for each item in a list.
Worked example
Python 3
numbers=[3,8,2,9,4]largest=numbers[0]forninnumbers:ifn>largest:largest=nprint("looked at",n,"- largest so far is",largest)print("answer:",largest)
Predict the output first, then show it
Expected output
looked at 3 - largest so far is 3
looked at 8 - largest so far is 8
looked at 2 - largest so far is 8
looked at 9 - largest so far is 9
looked at 4 - largest so far is 9
answer: 9
Step by step
numbers = [3, 8, 2, 9, 4] makes a list of five numbers and gives it the name numbers. The single = does not mean "equal" as in school maths. It means "put the value on the right under the name on the left".
numbers[0] is the item at position 0, the first one. Python counts positions from 0, so the last of five items is at position 4. The line largest = numbers[0] sets largest to 3.
for n in numbers: repeats the indented lines below it once for each item, and n holds the current item. The lines pushed in by four spaces are the body of the loop. Indentation is how Python knows which lines belong to the loop.
if n > largest: asks a question. If n is bigger than largest, the next indented line runs and largest = n gives largest a new value. If not, that line is skipped.
print(...) shows values on the screen. It is indented to the same level as the if, so it runs once per item. The last print is not indented, so it runs once, after the loop has finished.
The trace: largest starts at 3. Item 3 is not bigger, so largest stays 3. Item 8 is bigger, so largest becomes 8. Item 2: stays 8. Item 9: becomes 9. Item 4: stays 9. The answer is 9.
Common mistakes
Wrong
if n = largest:
A single = puts a value under a name. It cannot ask a question, so Python stops with a SyntaxError. To ask "are these equal?" write two equals signs. To ask "is n bigger?" write >.
Right
if n == largest:
Wrong
largest = 0
for n in numbers:
if n > largest:
largest = n
This breaks when every number is negative. With numbers = [-5, -2, -9] no number is bigger than 0, so the answer stays 0, which is not even in the list. Start from a real item of the list instead.
Right
largest = numbers[0]
Wrong
largest = numbers[5]
The list has five items, at positions 0 to 4. Position 5 does not exist, so Python stops with IndexError: list index out of range. The most common cause is counting from 1 instead of 0.
Right
largest = numbers[4]
Wrong
for n in numbers:
largest = n
if n > largest:
print("new largest")
Assigning before testing means n is already equal to largest when the test runs, so the test is never true. At the end largest is just the last item, 4, not 9. Tracing this by hand shows it at once. The order of the steps matters.
Right
for n in numbers:
if n > largest:
largest = n
Check yourself
Trace the algorithm by hand on [5, 1, 7]. What is largest after each of the three items?
Try it first, then show the answer
After 5: 5. After 1: still 5, because 1 is not bigger. After 7: 7. The answer is 7.
Change the algorithm so it finds the smallest number. What is the smallest change?
Try it first, then show the answer
Change > to <, so a number replaces the current one when it is smaller. Renaming largest to smallest keeps the code honest. On [3, 8, 2, 9, 4] the answer is 2.
What goes wrong if numbers is the empty list []? What does that say about the specification?
Try it first, then show the answer
numbers[0] fails with IndexError: list index out of range, because there is no first item. The specification must say the list has at least one number. A condition on the input is part of the specification.
02
Counting steps
Goal After this you can count the steps an algorithm takes on a given input, and say why we count steps instead of seconds.
How fast is an algorithm? Seconds are a poor answer. The same program takes different seconds on a phone, on a laptop and on a server, and different seconds again when other programs are running. So we count steps. A step is one small action, such as comparing two numbers or adding two numbers. The count does not depend on the machine.
You choose what to count, and you say what you chose. For finding the largest number you might count comparisons. For adding up a list you might count additions. Pick the action that does the real work and count it the same way every time.
The count depends on the input size, the amount of data. For a list we call the input size n, the number of items. A list of 5 items and a list of 5000 items give different counts. So the count is a rule that takes n and gives a number of steps.
The count can also depend on which input of size n you are given. Take a search for a value in a list. If the value is the first item, the search stops after 1 step. If it is the last item, or not in the list at all, the search looks at every item. The best case is the fewest steps over all inputs of size n. The worst case is the most steps. We usually quote the worst case, because it is a promise: the algorithm never takes more than that.
The example uses two Python tools. A function is a named group of steps. You make one with def. Its parameters are the inputs it receives. The word return hands back an answer and ends the function at once, even in the middle of a loop. A counter is a variable that starts at 0 and gets 1 added each time the thing you are counting happens.
New words
step
One small action that you choose to count, such as one comparison.
input size (n)
How much data there is. For a list, n is the number of items.
best case
The fewest steps over all inputs of size n.
worst case
The most steps over all inputs of size n. It is the promise that it never takes more.
counter
A variable that starts at 0 and goes up by 1 each time the counted event happens.
function
A named group of steps. Parameters are its inputs; return hands back its answer.
Worked example
Python 3
defsearch_steps(items,target):steps=0foriteminitems:steps+=1ifitem==target:returnstepsreturnstepsprint("size first last missing")forsizein[5,10,20]:items=list(range(1,size+1))print(size,search_steps(items,1),search_steps(items,size),search_steps(items,0))
Predict the output first, then show it
Expected output
size first last missing
5 1 5 5
10 1 10 10
20 1 20 20
Step by step
def search_steps(items, target): starts a function with two parameters: the list to search and the value to look for. The indented lines below it are its body.
steps = 0 sets up the counter. steps += 1 means steps = steps + 1, so it adds one to the counter. It runs once for every item that gets looked at.
If the item equals the target, return steps hands back the count and ends the function at once. If the loop finishes without finding the target, the last line return steps hands back the count, which is now the length of the list.
range(1, size + 1) gives the whole numbers from 1 up to size. list(...) turns that into a list. For size 5 the list is [1, 2, 3, 4, 5].
Each row calls the function three times. Target 1 is the first item. Target size is the last item. Target 0 is not in the list at all.
Read the table. The first column of counts is always 1, whatever the size. The other two always equal the size. So the best case is 1 step and the worst case is n steps.
Common mistakes
Wrong
for item in items:
steps = 0
steps += 1
The counter is reset to 0 on every pass, so it always ends at 1. Set the counter once, before the loop starts, and only add to it inside the loop.
Right
steps = 0
for item in items:
steps += 1
Wrong
if item == target:
steps += 1
This counts how many items match, not how many items were looked at. The question was how many steps the search takes, so every item that is examined must be counted, matching or not.
Right
steps += 1
if item == target:
return steps
Wrong
search_steps([7, 2, 9], 7) # gives 1, so "a search always takes 1 step"
One input shows only one case, here the best case. A claim about the worst case needs the worst input: the target last, or missing. Always try the best, the worst, and something in between.
Right
search_steps([7, 2, 9], 9) # gives 3: try the last item and a missing value too
Wrong
for item in items:
steps += 1
if item == target:
return steps
return steps
The second return is indented as far as the if, so it sits inside the loop. The function ends after the first item whatever happens, and every search reports 1 step. The final return belongs after the loop, at the same indentation as the for line.
Right
for item in items:
steps += 1
if item == target:
return steps
return steps
Check yourself
How many steps does search_steps([4, 4, 4, 4], 4) take, and why?
Try it first, then show the answer
1 step. The first item already equals the target, so return runs at once. The other three items are never looked at.
A list has 1000 items. How many steps does the search take in the worst case? And a list of 2000 items?
Try it first, then show the answer
1000 and 2000. The worst case is n steps, so doubling the list doubles the worst-case count.
Write a counter that counts how many numbers in [3, 8, 2, 9, 4] are greater than 5. What count do you expect?
Try it first, then show the answer
count = 0, then for n in numbers: if n > 5: count += 1. The expected count is 2, for 8 and 9. Here the addition belongs inside the if, because this time we do want to count only the matches.
03
Growth and big-O
Goal After this you can compare two step counts by how fast they grow, and read O(n) and O(n²) as statements about growth.
Lesson 2 gave step counts such as n and 2n + 5. The question that matters is not the count for one n. It is what happens to the count when the input gets bigger. Growth means how fast the step count rises as n rises.
Take two algorithms. Algorithm A takes 100 steps for each item, so 100n steps in all. Algorithm B takes n steps for each of n items, so n times n steps, written n². With 10 items, A needs 1000 steps and B needs only 100, so B looks better. With 100 items they tie at 10,000. With 1000 items A needs 100,000 and B needs 1,000,000. B is now ten times worse, and the gap keeps widening. Whatever fixed number you put in front of n, an n² algorithm eventually loses to an n algorithm.
That is why we ignore fixed multipliers and small extra terms, and keep only the part that grows fastest. The count 3n + 10 grows like n. The count n² + 5n + 7 grows like n². Big-O is the notation for this. Writing O(n) says: the step count is at most a fixed multiple of n, once n is big enough. For example, 3n + 10 is at most 4n whenever n is 10 or more. At n = 10 both are 40, and after that 4n is the bigger one. Here the fixed multiple is 4 and "big enough" means 10 or more.
Doubling is the quickest way to read growth. If an algorithm is O(n), doubling n roughly doubles the steps. If it is O(n²), doubling n roughly quadruples them, because 2 times 2 is 4. If it is O(1), the steps do not change at all, like reading the first item of a list.
A few more names. O(log n) grows very slowly. Think of the number of times you can halve n before you reach 1. For n = 1,000,000 that is only about 20, because 2 multiplied by itself 20 times is about a million. O(n log n) is a little more than n. O(2ⁿ) doubles with every extra item. The number 2 multiplied by itself 1000 times already has 302 digits. From slowest growth to fastest: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
Big-O describes growth, not seconds, and not small inputs. For small n an algorithm with worse growth may be faster. Big-O tells you who wins when n is large.
New words
growth
How fast the step count rises as n rises.
big-O, O(...)
O(n) says the step count is at most a fixed multiple of n once n is big enough.
n squared (n²)
n times n. Doubling n makes it four times bigger.
O(1)
A fixed number of steps that does not depend on n.
halving
Dividing by 2 again and again. The number of halvings before reaching 1 is about log n.
Worked example
Python 3
print("n A=100*n B=n*n fewer-steps")fornin[10,50,100,200,1000]:a=100*nb=n*nifa<b:winner="A"elifa>b:winner="B"else:winner="tie"print(n,a,b,winner)print("doubling n from 1000 to 2000:")print("A grows by a factor of",(100*2000)//(100*1000))print("B grows by a factor of",(2000*2000)//(1000*1000))
Predict the output first, then show it
Expected output
n A=100*n B=n*n fewer-steps
10 1000 100 B
50 5000 2500 B
100 10000 10000 tie
200 20000 40000 A
1000 100000 1000000 A
doubling n from 1000 to 2000:
A grows by a factor of 2
B grows by a factor of 4
Step by step
a = 100 * n and b = n * n compute the step counts of algorithm A and algorithm B for the current n. The star * means multiply.
if, elif and else make a chain of questions. Python asks them in order and runs only the first one that is true. elif means "else if". Here the chain picks which count is smaller.
The table: at n = 10 and n = 50, B has fewer steps. At n = 100 they tie. From n = 200 on, A has fewer steps, and the gap grows. B wins only on small inputs.
The // sign divides and drops any fraction, so the result is a whole number. Dividing the new count by the old count shows the growth factor.
When n doubles from 1000 to 2000, A takes 2 times as many steps and B takes 4 times as many. That is the difference between O(n) and O(n²).
Common mistakes
Wrong
# steps = 3n + 10, so the algorithm is O(3n + 10)
Inside O( ) we keep only the part that grows fastest and drop its fixed multiplier. The count 3n + 10 is written O(n). A fixed multiplier such as 3 and a small extra term such as 10 do not change how the count grows.
Right
# steps = 3n + 10, so the algorithm is O(n)
Wrong
print(10 ^ 2) # prints 8
In Python the ^ sign is not "to the power of". It combines the binary digits of two numbers, and for 10 and 2 the result is 8. Powers are written with two stars. This matters whenever you write n squared in code.
Right
print(10 ** 2) # prints 100
Wrong
print(10 * 9 / 2) # prints 45.0
A single / always gives a decimal number, even when the answer is whole. Step counts are whole numbers, so the output 45.0 looks wrong and can break later code that expects a whole number. Use // for whole-number division.
Right
print(10 * 9 // 2) # prints 45
Wrong
# at n = 10: n*n is 100 and 100*n is 1000, so "n*n is the faster one"
One small n tells you nothing about growth. Compare at large n, or double n and watch the factor. At n = 1000, n*n is 1,000,000 and 100*n is only 100,000. Big-O is a statement about large n.
Right
# at n = 1000: n*n is 1000000 and 100*n is 100000, so 100*n wins for large n
Check yourself
Write each step count in its simplest big-O form: (a) 5n + 20, (b) n² + 50n, (c) 7.
Try it first, then show the answer
(a) O(n). (b) O(n²), because n² beats 50n once n is large. (c) O(1): a fixed count that does not depend on n.
An algorithm takes n² steps. It takes 90,000 steps on a list of 300 items. About how many steps on 600 items?
Try it first, then show the answer
Doubling n makes n² four times bigger, so 4 times 90,000 is 360,000. Check: 600 times 600 is 360,000.
Use Python to compute 100*n and n*n at n = 99 and at n = 101. Which has fewer steps each time?
Try it first, then show the answer
At n = 99: 100*n is 9900 and n*n is 9801, so B has fewer. At n = 101: 100*n is 10100 and n*n is 10201, so A has fewer. The winner switches just after n = 100.
04
Recursion from zero
Goal After this you can read and write a short recursive function, and say why it stops.
Recursion means a function solves a problem by calling itself on a smaller version of the same problem. A function that calls itself is called recursive.
Think of counting the people standing behind you in a queue. You do not count them all yourself. You ask the person behind you, "how many people are behind you?" That person asks the next one, and so on. The last person in the queue says "none", which is 0. Then each person answers the one in front with "my answer plus 1". The answers travel back up the queue until you get yours.
Every recursive function needs two parts. The base case is a smallest problem that you can answer directly, with no further call. The recursive case solves a bigger problem by calling the function on a smaller one and then using that answer. If there is no base case, or if the call does not get smaller, the calls never stop.
Our problem is to add up the numbers from 1 to n. Call the answer sum_to(n). The base case: sum_to(0) is 0, because there is nothing to add. The recursive case: sum_to(n) is n plus sum_to(n - 1). For example, sum_to(3) is 3 + sum_to(2), which is 3 + (2 + sum_to(1)), which is 3 + (2 + (1 + sum_to(0))). That is 3 + (2 + (1 + 0)), which is 6.
How do you trust that this works? Trust the smaller call. When you write the recursive case, assume sum_to(n - 1) already gives the right answer, and check that your line turns it into the right answer for n. Then check the base case. Lesson 6 turns this habit into a proof.
Python keeps every call that is still waiting for an answer. In the example each call prints when it starts and when it finishes, so you can watch the waiting calls pile up and then finish in reverse order. Python allows about a thousand calls to wait at once. Beyond that it stops with a RecursionError. The number of calls for sum_to(n) is n + 1, so recursion has a step count too: this one is O(n).
New words
recursion
A function solving a problem by calling itself on a smaller version of the problem.
base case
The smallest problem, answered directly with no further call.
recursive case
The part that calls the function on a smaller problem and uses the answer.
call
One use of a function. Each call has its own copy of the parameters.
def sum_to(n): defines the function. The first line of the body prints "start" and the value of n, so each call announces itself.
if n == 0: is the base case. It prints a message and returns 0 at once. No further call is made, so the chain of calls ends here.
answer = n + sum_to(n - 1) is the recursive case. The function calls itself with a smaller number, and the current call waits on this line until that smaller call returns.
The call then prints "finish", and return answer hands the result to whoever called it. Each call has its own n, so the calls do not mix up their values.
Read the output top to bottom. The four "start" lines go 3, 2, 1, 0: the calls pile up. Then the base case returns 0. The call for 1 finishes with 1 + 0 = 1, the call for 2 finishes with 2 + 1 = 3, the call for 3 finishes with 3 + 3 = 6.
The last line, 6, comes from the print outside the function: print(sum_to(3)) shows what the outermost call returned.
Common mistakes
Wrong
def sum_to(n):
return n + sum_to(n - 1)
There is no base case, so nothing ever stops the calls. Python waits for the thousandth call, then stops with RecursionError: maximum recursion depth exceeded. Every recursive function needs a case that returns without calling itself.
Right
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
Wrong
return n + sum_to(n)
The call uses the same n, so the problem never gets smaller. The base case is never reached and the result is the same RecursionError. The recursive call must move toward the base case.
Right
return n + sum_to(n - 1)
Wrong
def sum_to(n):
if n == 0:
return 0
n + sum_to(n - 1)
The last line works out a number and throws it away, because there is no return. A function with no return gives back None. So sum_to(1) gives None instead of 1, and sum_to(2) stops with TypeError, because 2 + None is not allowed.
Right
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
Wrong
if n == 0:
return 1
The base case must give the right answer for the smallest problem. The sum of no numbers is 0, not 1. With this line every answer is off by one: sum_to(3) comes out as 7 instead of 6. A wrong base case spoils every bigger answer built on it.
Right
if n == 0:
return 0
Check yourself
Trace sum_to(2) by hand. Which calls happen, and what does each one return?
Write a recursive function factorial(n) that multiplies 1 * 2 * ... * n, with factorial(0) equal to 1. What is factorial(5)?
Try it first, then show the answer
def factorial(n): if n == 0: return 1, then return n * factorial(n - 1). The answer for factorial(5) is 120. The base case returns 1, not 0, because multiplying by 0 would turn every answer into 0.
What happens if you call sum_to(-1)? Why?
Try it first, then show the answer
The calls go to -2, -3, and so on, and n never equals 0. They never stop, so Python ends with a RecursionError. The function is only meant for n of 0 or more, and the specification should say so.
05
Proving a loop works with an invariant
Goal After this you can state a loop invariant in words and use three questions to argue that a loop gives the right answer.
Running an algorithm on a few inputs and seeing the right answers is testing. Testing can show that a bug exists. It can never show that there is none, because there are too many possible inputs. To be sure an algorithm is correct for every input you need an argument. For loops, the standard argument uses a loop invariant.
A loop invariant is a sentence about the variables that is true at the start of every pass through the loop. "Invariant" means "does not change": the variables change, but the sentence stays true. For finding the largest number, the invariant is: largest is the biggest of the first i numbers that have been looked at.
Three questions turn an invariant into an argument. Start: is the sentence true before the first pass? Keep: if it is true before a pass, is it still true after that pass? End: when the loop stops, does the sentence give the answer we want? If all three answers are yes, the loop is correct. It works like a staircase. The first step is solid (start), each step leads to the next (keep), and at the top you read off the answer (end).
There is a fourth question that is easy to forget: does the loop stop at all? A loop that never stops gives no answer, however good its invariant. A loop over a list stops because every pass moves on by one item and the list is finite.
The example writes the invariant as an assert. An assert line checks a claim. If the claim is true nothing happens. If it is false, Python stops with an AssertionError. Checking an assert on one input is still testing, not a proof. The proof is the three questions answered in words. The assert helps because it catches a wrong invariant early. Two notes about the code: numbers[:i] means the first i items of the list, and max(...) means the biggest item. The check uses max only to test our own steps.
New words
loop invariant
A sentence about the variables that is true at the start of every pass of the loop.
assert
A line that checks a claim and stops with AssertionError if the claim is false.
while loop
A loop that repeats as long as its condition is true.
correct
Gives an answer that meets the specification for every allowed input, not just the inputs tried.
Worked example
Python 3
numbers=[3,8,2,9,4]largest=numbers[0]i=1whilei<len(numbers):assertlargest==max(numbers[:i])ifnumbers[i]>largest:largest=numbers[i]i=i+1print("after pass: i =",i,"largest =",largest)assertlargest==max(numbers[:i])print("answer:",largest)
Predict the output first, then show it
Expected output
after pass: i = 2 largest = 8
after pass: i = 3 largest = 8
after pass: i = 4 largest = 9
after pass: i = 5 largest = 9
answer: 9
Step by step
i = 1 says that one number, numbers[0], has been looked at. while i < len(numbers): repeats the body as long as the condition is true. len(numbers) is the number of items, 5.
The invariant, written as an assert: largest is the biggest of numbers[:i], the first i items. The assert sits at the top of the body, so it checks the invariant at the start of every pass.
Start: before the first pass i is 1 and largest is numbers[0], which is the biggest of a list of one number. The sentence is true.
Keep: the if line compares the next number, numbers[i], with largest, so largest becomes the biggest of the first i + 1 numbers. Then i = i + 1 moves i up by one, and the sentence is true again for the new i.
End: i grows by 1 each pass, so it reaches 5 and the loop stops. With i = 5 the sentence says largest is the biggest of all five numbers, which is the answer. The assert after the loop checks it.
The output shows the sentence staying true as the variables change: for example after the first pass, i is 2 and largest is 8, the biggest of 3 and 8.
Common mistakes
Wrong
# invariant: largest is one of the numbers in the list
This sentence is true all the time, but it is too weak. When the loop ends it only says largest is some number from the list, which does not say it is the biggest. A useful invariant must give the answer at the end.
Right
# invariant: largest is the biggest of the first i numbers
Wrong
while i < len(numbers):
if numbers[i] > largest:
largest = numbers[i]
Nothing changes i, so the condition stays true and the loop never stops. On this page the run is stopped after 8 seconds. An invariant proves nothing about a loop that does not end, so always check that something moves the loop toward its end.
Right
while i < len(numbers):
if numbers[i] > largest:
largest = numbers[i]
i = i + 1
Wrong
if numbers[i] > largest:
largest = numbers[i]
assert largest == max(numbers[:i])
i = i + 1
The invariant is only promised at the start of a pass and after the last pass. In the middle of a pass it can be false. Here largest has already looked at numbers[i], but i has not moved yet, so with [3, 8, ...] the assert sees 8 against max([3]) and stops with AssertionError.
Right
assert largest == max(numbers[:i])
if numbers[i] > largest:
largest = numbers[i]
i = i + 1
Wrong
largest = 0
i = 1
This fails the start question. For numbers = [-5, -2, -9] the sentence says largest is the biggest of the first 1 number, which is -5, but largest is 0. The first assert stops with AssertionError. Begin from numbers[0], so the sentence is true before the first pass.
Right
largest = numbers[0]
i = 1
Check yourself
Write the invariant in words for: total = 0, then for x in numbers: total = total + x. Use "after k passes".
Try it first, then show the answer
After k passes, total is the sum of the first k numbers. Start: after 0 passes total is 0, the sum of no numbers. Keep: adding the next number gives the sum of the first k + 1. End: after all passes, total is the sum of all the numbers.
A loop starts with i = 0 and total = 0 and repeats while i < 4: total = total + i, then i = i + 1. State an invariant, and say what total is when the loop stops.
Try it first, then show the answer
Invariant: total is 0 + 1 + ... + (i - 1), the sum of the whole numbers below i. The loop stops when i is 4, and then total is 0 + 1 + 2 + 3 = 6.
A friend says: "I ran it on 100 lists and every answer was right, so it is correct." Why is that not enough?
Try it first, then show the answer
Testing checks only the inputs you tried. The argument covers every input. The bug may sit in a list nobody tried, such as one with only negative numbers, which is exactly what starting with largest = 0 gets wrong.
06
Proof by induction from zero
Goal After this you can prove a claim about every whole number n by checking a base case and a step.
Some claims are about every whole number: 0, 1, 2, 3, and so on for ever. Testing can check only some of them. Induction proves all of them with two checks. The picture is a long row of dominoes. If you can show that the first domino falls, and that every domino that falls knocks over the next one, then every domino falls.
Write P(n) for the claim about the number n. For example, P(n) might say "1 + 2 + ... + n equals n(n + 1)/2". An induction has two parts. The base case: show that P(0) is true, or P for the smallest n you care about. The inductive step: take any whole number k, assume P(k) is true, and show that P(k + 1) is true. The assumption "P(k) is true" is called the inductive hypothesis.
Do not worry that you are assuming something that looks like the thing to prove. You assume the claim for one number k only, and use it to reach the next number, k + 1. That is the domino again: a domino can only fall if the one before it has fallen.
Here is the example. Claim: 1 + 2 + ... + n = n(n + 1)/2. Base case, n = 0: the left side is 0, because it adds nothing, and the right side is 0 times 1 divided by 2, which is 0. They match. Step: assume 1 + ... + k = k(k + 1)/2. Then 1 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1). Taking out the common factor k + 1 gives (k + 1)(k/2 + 1), which is (k + 1)(k + 2)/2. That is exactly the formula for k + 1. So the claim holds for every n.
Recursion and induction have the same shape. The function sum_to from lesson 4 has a base case and a step that uses the smaller answer. Induction is the proof that such a function gives the right answer. The base case of the proof matches the base case of the function, and the inductive hypothesis is the habit of trusting the smaller call.
The Python example checks the base case and 100 steps by brute force, which means trying every case in a small range. That is a sanity check, not the proof. The proof is the algebra above, which covers every k at once.
New words
induction
A proof that a claim holds for every whole number, using a base case and a step.
base case
Showing the claim for the smallest number, usually 0 or 1.
inductive step
Showing that if the claim holds for k, it holds for k + 1.
inductive hypothesis
The assumption, inside the step, that the claim holds for k.
brute force
Trying every case in a small range. It can find a counterexample but cannot prove a claim for all n.
Worked example
Python 3
defsum_to(n):ifn==0:return0returnn+sum_to(n-1)forninrange(5):print(n,sum_to(n),n*(n+1)//2)# Base case: n = 0assertsum_to(0)==0*(0+1)//2# Step: if the formula holds for k, it holds for k + 1.forkinrange(100):formula_k=k*(k+1)//2assertformula_k+(k+1)==(k+1)*(k+2)//2print("base case and 100 steps checked")
Predict the output first, then show it
Expected output
0 0 0
1 1 1
2 3 3
3 6 6
4 10 10
base case and 100 steps checked
Step by step
sum_to is the recursive function from lesson 4. The first loop prints n, the value sum_to(n) computes, and the value of the formula n(n + 1)/2. range(5) gives 0, 1, 2, 3, 4. The last two columns agree on every row.
Lines that start with # are comments. Python ignores them, and they are there for people. The assert under "# Base case" checks that the claim holds at n = 0. Both sides are 0.
The second loop does the inductive step with numbers. For each k from 0 to 99 it takes the formula value for k, adds the next number k + 1, and checks that the result equals the formula value for k + 1.
If any assert failed, Python would stop with AssertionError. Since none does, the program prints the last line.
Notice what this does not do. It checks 100 values of k. The algebra in the explanation covers all of them at once, and that difference is the point of a proof.
Common mistakes
Wrong
# Claim: n*n + n is odd for every n.
# Step: if k*k + k is odd, then adding 2*(k+1) keeps it odd. (true)
# So the claim holds for every n.
The step is correct, but the base case was never checked. At n = 0 the value is 0, which is even, so the claim is false. In fact n*n + n is even for every n. A step with no base case is a row of dominoes where nobody pushed the first one.
Right
print(0 * 0 + 0) # 0 is even, so the claim fails at n = 0
Wrong
# n*n + n + 41 is prime for n = 0, 1, 2, ..., 39
# so it is prime for every n
Many successful checks are not a proof. This formula really does give a prime for each n from 0 to 39, and then fails: at n = 40 it gives 1681, which is 41 times 41. Only the step argument covers every n. A test can disprove a claim, but it cannot prove one.
Right
print(40 * 40 + 40 + 41, 41 * 41) # 1681 1681
Wrong
Assume P(k + 1). Then P(k + 1) is true.
This assumes the very thing the step must show, so it proves nothing. The inductive hypothesis is about k, the number before. The step must start from P(k) and arrive at P(k + 1) using real reasoning, such as the algebra above.
Right
Assume P(k). Show P(k + 1), using the assumption.
Check yourself
Prove by induction that 1 + 3 + 5 + ... + (2n - 1) = n² for n = 1, 2, 3, ...
Try it first, then show the answer
Base case n = 1: the left side is 1 and the right side is 1². Step: assume the sum of the first k odd numbers is k². The next odd number is 2(k + 1) - 1 = 2k + 1. Then k² + 2k + 1 = (k + 1)², which is the claim for k + 1. So it holds for every n.
In the domino picture, what do the base case and the inductive step stand for?
Try it first, then show the answer
The base case is the first domino falling. The inductive step is "if one domino falls, it knocks over the next one". You need both: without the first push nothing falls, and without the step the fall stops.
A friend ran a Python loop for n = 1 to 1,000,000, the claim held every time, and says "that is proof by induction". What is wrong?
Try it first, then show the answer
That is brute force, which is testing. Induction needs a base case and an argument for the step that works for any k. The prime-looking formula in the mistakes above passes 40 checks and then fails, so a long run of successes proves nothing about the next case.