Answer key · Unit 4

Algorithms and efficiency.

Each lesson’s practice questions, their correct answers and the mistakes they spot. Answers read off the Scene use the same setting the learner sees.

Misconception catalogue

Answer key 4

Lesson 1 of 4 · About 25 minutes

The steps of an algorithm

What an algorithm is, through one way to sort: bubble sort compares neighbours and swaps them, pass after pass. Count the comparisons and swaps, and see how the starting row changes the work.

Open the lesson

The 6 steps and their answers

Step 1 of 6
Open this step
Exact steps
Practice · Choose
Question
What makes a list of instructions an algorithm?

Correct answer
- Correct The steps are exact, involve no guessing, and always end with the answer
Setup, choices and feedback
The Scene at this step
Algorithm
Bubble
List size
8 blocks
Starting order
Shuffled
Show how it grows
Blocks
Choices
Shown in a random order.
- Correct The steps are exact, involve no guessing, and always end with the answer
- Wrong They are written in a programming language
  Misconception: Takes an algorithm to be a program written in a programming language, rather than the exact steps any person or machine could follow.
  Feedback from the catalogue
  An algorithm is the method, not the code. A cake recipe, long division in a notebook and bubble sort are all algorithms, because each is a finite list of exact steps that always reaches the answer. A program is an algorithm written in a language a computer understands; the same algorithm can be written in any language, or carried out by hand.
- Wrong They reach the answer fast
  Feedback
  There are very slow algorithms, which is exactly why we compare them. Speed is a property of an algorithm, not the condition for being one.
- Wrong They give a right answer most of the time
  Feedback
  An algorithm has to work every time, on every input of the kind it takes. A method that works “usually” is a rule of thumb.
Feedback for a right answer
An algorithm is a finite list of exact steps, ones anybody, person or machine, can carry out without thinking, that always ends with the right answer. Bubble sort is one: “compare two neighbours; if the left is taller, swap them; move on to the next pair.”

Worked solution
1. Exact: at every step it is clear what to do, with no judgement.
2. Finite: the steps run out.
3. Correct: on every input the answer is right.
A programming language is only one way to write an algorithm down; bubble sort can be carried out by hand, with real blocks.
Step 2 of 6
Open this step
One pass
Practice · Calculate
Question
The row has 8 blocks. In bubble sort’s first pass each block is compared with its right-hand neighbour, left to right. How many comparisons does that pass make?

Correct answer
7 ± 0.01
Setup, choices and feedback
The Scene at this step
Algorithm
Bubblefixed
List size
8 blocks
Starting order
Shuffled
Show how it grows
Blocks
Accepted within
± 0.01
A fixed value in the question
Feedback for a right answer
Seven: eight blocks have seven pairs of neighbours, as eight posts in a fence have seven gaps between them.

Hint
How many pairs of neighbours does a row of eight have?

Worked solution
1. The pairs: blocks 1 and 2, 2 and 3, and so on up to 7 and 8.
2. The last block has no neighbour on its right.
3. So there are $8 - 1 = 7$ ⁠ comparisons.
If you answered $8$ ⁠, you counted a comparison per block; a comparison is between a pair.
Step 3 of 6
Open this step
The tallest drifts to the end
Practice · Choose
Question
Bubble sort has finished its first pass. What is certainly true now?

Correct answer
- Correct The tallest block stands at the right end
Setup, choices and feedback
The Scene at this step
Algorithm
Bubblefixed
List size
8 blocks
Starting order
Shuffled
Show how it grows
Blocks
Choices
Shown in a random order.
- Correct The tallest block stands at the right end
- Wrong The whole row is sorted
  Misconception: Thinks a single pass of bubble sort along the row leaves it sorted.
  Feedback from the catalogue
  One pass of bubble sort guarantees only one thing: the tallest block drifts to the right end. Every other block moves at most one place left. So another pass is needed, and another, each stopping one place sooner than the last. A reversed row of eight blocks takes seven passes: $7 + 6 + \cdots + 1 = 28$ ⁠ comparisons.
- Wrong The shortest block stands at the left end
  Feedback
  The shortest block moves at most one place left per pass: it wins only one comparison, with its left-hand neighbour.
Feedback for a right answer
Once the tallest block enters a comparison it wins every comparison after it and is swapped right again and again, to the end. That is why the next pass can stop one place sooner.

Worked solution
1. A pass compares neighbours left to right, and swaps when the left one is taller.
2. The tallest block is taller than any neighbour, so from its first comparison it keeps moving right.
3. At the end of the pass it is at the right end. About the other blocks the pass promises nothing.
A reversed row needs seven such passes before everything is sorted.
Step 4 of 6
Open this step
Every pair
Practice · Calculate
Question
Algorithm is Bubble, List size 8, and Starting order Reversed: the tallest block first. How many comparisons will the whole sort make?

Correct answer
28 ± 0.01
Setup, choices and feedback
The Scene at this step
Algorithm
Bubblefixed
List size
8 blocksfixed
Starting order
Reversedfixed
Show how it grows
Blocks
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons
Wrong answers it recognises
- 64 ± 0.01
  Misconception: Counts n × n comparisons for comparing every pair, counting each pair twice and a block against itself.
  Feedback from the catalogue
  To compare every pair once, each block meets each of the other $n - 1$ ⁠, which is $n(n-1)$ ⁠, but that counts every pair twice, once from each side. So the number of pairs is $\dfrac{n(n-1)}{2}$ ⁠: for eight blocks $\dfrac{8 \times 7}{2} = 28$ ⁠, not $64$ ⁠. It grows like $n^2$ ⁠, but it is not $n^2$ ⁠ itself.
- 7 ± 0.01
  Misconception: Thinks a single pass of bubble sort along the row leaves it sorted.
  Feedback from the catalogue
  One pass of bubble sort guarantees only one thing: the tallest block drifts to the right end. Every other block moves at most one place left. So another pass is needed, and another, each stopping one place sooner than the last. A reversed row of eight blocks takes seven passes: $7 + 6 + \cdots + 1 = 28$ ⁠ comparisons.
Feedback for a right answer
$7 + 6 + 5 + 4 + 3 + 2 + 1 = 28$ ⁠. In a reversed row every pass finds something to swap, so the sort never stops early: seven passes, each one shorter than the last.

Hint
How many comparisons does each pass make, and how many passes are there?

Worked solution
1. The first pass: $7$ ⁠ comparisons, and the tallest reaches the end.
2. Each further pass stops one place sooner: $6$ ⁠, $5$ ⁠, …, $1$ ⁠.
3. The sum: $7 + 6 + \cdots + 1 = \dfrac{8 \times 7}{2} = 28$ ⁠.
If you answered $64$ ⁠, you counted $8 \times 8$ ⁠: a block against itself, and every pair twice. If you answered $7$ ⁠, you stopped after one pass.
Step 5 of 6
Open this step
Counting swaps
Practice · Calculate
Question
On the same reversed row of 8 blocks, how many swaps will bubble sort make?

Correct answer
28 ± 0.01
Setup, choices and feedback
The Scene at this step
Algorithm
Bubblefixed
List size
8 blocksfixed
Starting order
Reversedfixed
Show how it grows
Blocks
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Swaps the whole sort makes (merge sort moves instead and makes none)/nodes/sort/outputs/swaps
Wrong answers it recognises
- 64 ± 0.01
  Misconception: Counts n × n comparisons for comparing every pair, counting each pair twice and a block against itself.
  Feedback from the catalogue
  To compare every pair once, each block meets each of the other $n - 1$ ⁠, which is $n(n-1)$ ⁠, but that counts every pair twice, once from each side. So the number of pairs is $\dfrac{n(n-1)}{2}$ ⁠: for eight blocks $\dfrac{8 \times 7}{2} = 28$ ⁠, not $64$ ⁠. It grows like $n^2$ ⁠, but it is not $n^2$ ⁠ itself.
Feedback for a right answer
28, the same as the comparisons: in a reversed row every pair of blocks is in the wrong order, and each swap of neighbours fixes exactly one pair.

Hint
In how many of the comparisons on a reversed row is the left block taller?

Worked solution
1. An “inverted” pair is two blocks with the taller on the left. In a reversed row all $\dfrac{8 \times 7}{2} = 28$ ⁠ pairs are inverted.
2. Swapping two neighbours fixes their pair and changes no other pair.
3. So exactly $28$ ⁠ swaps are needed.
If you answered $4$ ⁠, you swapped the ends with each other, as you would reversing by hand. Bubble sort swaps only neighbours.
Step 6 of 6
Open this step
Stopping early
Practice · Predict, then look
Question
Starting order will change to Nearly sorted: 2 1 3 4 5 6 7 8, with only the first two blocks out of order. Bubble sort stops after a pass that swaps nothing. How many comparisons will it make?

Correct answer
13 ± 0.01
A number prediction counts as right within ± 0.01
Setup, choices and feedback
The Scene at this step
Algorithm
Bubblefixed
List size
8 blocksfixed
Starting order
Reversedfixed
Show how it grows
Blocks
Once the prediction is locked in, the Scene changes
Starting order
Nearly sortedfixed
The Scene then shows: 13 · Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
$7 + 6 = 13$ ⁠. The first pass swaps 2 and 1 and leaves the row sorted; the second pass finds nothing to swap, and the sort stops. 13 instead of 28.

Worked solution
1. First pass: $7$ ⁠ comparisons, one swap, and the row is sorted.
2. Second pass: $6$ ⁠ comparisons, no swap.
3. A pass with no swap means the row is sorted, so it stops: $7 + 6 = 13$ ⁠.
The starting row changes the work: the same algorithm, the same eight blocks, less than half the comparisons.

Lesson 2 of 4 · About 25 minutes

Comparing sorts

Four methods for one problem: bubble, insertion, merge and quicksort. Measure how many comparisons each makes on the same row, find that the number of swaps is fixed, and see that even a fast method has a worst case.

Open the lesson

The 5 steps and their answers

Step 1 of 5
Open this step
Four ways
Practice · Predict, then look
Question
Sixteen blocks, Nearly sorted. Which Algorithm will sort this row in the fewest comparisons?

Correct answer
- Correct Insertion
Setup, choices and feedback
The Scene at this step
Algorithm
Bubble
List size
16 blocksfixed
Starting order
Nearly sortedfixed
Show how it grows
Blocks
Choices
- Correct Insertion
- Wrong Quick
  Misconception: Thinks quicksort is always the fastest sort, whatever the starting row.
  Feedback from the catalogue
  Quicksort is fast on average, on a shuffled row. The version here always takes the last block as its pivot, and on a sorted or reversed row that block is the tallest or the shortest: each partition removes only one block, and the sort makes $\dfrac{n(n-1)}{2}$ ⁠ comparisons, as many as bubble sort. Real library sorts pick a random or median pivot to avoid this.
- Wrong Merge
  Feedback
  Merge sort does about the same work on any row: it splits and merges either way. Here 34 comparisons.
- Wrong Bubble
  Feedback
  Bubble sort stops early, but only after a whole pass without swaps, and a block that must move left moves one place per pass. Here 42 comparisons.
Once the prediction is locked in, the Scene changes
Algorithm
Insertion
The Scene then shows: 19 · Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Insertion, with only 19 comparisons. Each new block slides left only until it meets a shorter one, and in a nearly sorted row that is almost at once. Quicksort, by contrast, makes 109 here.

Worked solution
1. Insertion sort takes block after block and slides it left while its neighbour is taller.
2. In a nearly sorted row most blocks are already in place: one comparison, and it stops.
3. So the work is close to $n - 1 = 15$ ⁠ comparisons, plus a few for the blocks that moved.
Quicksort with the last block as pivot struggles precisely on sorted rows: each partition removes one block.
Step 2 of 5
Open this step
Merge sort
Practice · Calculate
Question
Merge on a Reversed row of 8 blocks. Bubble sort made 28 comparisons here. How many comparisons will merge sort make?

Correct answer
12 ± 0.01
Setup, choices and feedback
The Scene at this step
Algorithm
Mergefixed
List size
8 blocksfixed
Starting order
Reversedfixed
Show how it grows
Blocks
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons
Wrong answers it recognises
- 28 ± 0.01
  Misconception: Thinks every sorting algorithm does the same amount of work on the same list, since they all end with the same sorted row.
  Feedback
  28 is bubble sort’s count. Different algorithms do different amounts of work on exactly the same row.
- 64 ± 0.01
  Misconception: Counts n × n comparisons for comparing every pair, counting each pair twice and a block against itself.
  Feedback from the catalogue
  To compare every pair once, each block meets each of the other $n - 1$ ⁠, which is $n(n-1)$ ⁠, but that counts every pair twice, once from each side. So the number of pairs is $\dfrac{n(n-1)}{2}$ ⁠: for eight blocks $\dfrac{8 \times 7}{2} = 28$ ⁠, not $64$ ⁠. It grows like $n^2$ ⁠, but it is not $n^2$ ⁠ itself.
Feedback for a right answer
When two sorted halves are merged, each comparison lowers one block to the bottom shelf. In a reversed row every block in the right half is shorter than every one in the left, so the comparisons run out when the right half does: $4 + 4 + 4 = 12$ ⁠.
Hint
In how many levels are eight blocks split, and how many comparisons does each level cost on a reversed row?

Worked solution
1. Merge sort splits the eight into halves, quarters and single blocks: three levels, $\log_2 8 = 3$ ⁠.
2. At each level pairs of pieces are merged. In a reversed row, merging two pieces of size $k$ ⁠ costs $k$ ⁠ comparisons.
3. At the bottom level four merges of $1$ ⁠, in the middle two of $2$ ⁠, at the top one of $4$ ⁠: $4 + 4 + 4 = 12$ ⁠.
If you answered $28$ ⁠, you assumed every sort does the same work. It does not: that is why algorithms are compared.
Step 3 of 5
Open this step
Swaps and inverted pairs
Practice · Predict, then look
Question
On this shuffled row of 16 blocks, bubble sort makes 72 swaps. Algorithm will change to Insertion, which also swaps only neighbours. How many swaps will it make?

Correct answer
- Correct Exactly 72
Setup, choices and feedback
The Scene at this step
Algorithm
Bubble
List size
16 blocksfixed
Starting order
Shuffledfixed
Show how it grows
Blocks
Choices
- Correct Exactly 72
- Wrong Fewer, because insertion sort is faster
  Feedback
  Insertion sort makes fewer comparisons here, 85 instead of 120. But each swap of neighbours fixes one inverted pair, and both sorts have to fix all the inverted pairs.
- Wrong More
  Feedback
  Neither swaps for nothing: each swap fixes one inverted pair, and the number of inverted pairs is fixed by the row.
Once the prediction is locked in, the Scene changes
Algorithm
Insertion
The Scene then shows: 72 · Swaps the whole sort makes (merge sort moves instead and makes none)/nodes/sort/outputs/swaps
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
72: exactly the number of inverted pairs in the row. Each swap of two neighbours fixes one pair and spoils no other, so every sort that swaps only neighbours makes exactly the same number of swaps. What sets them apart is the comparisons.

Worked solution
1. An inverted pair: two blocks with the taller on the left. This row has $72$ ⁠ of them.
2. Swapping neighbours reverses the order of their pair only: the count of inverted pairs drops by one.
3. A sorted row has $0$ ⁠ inverted pairs, so any neighbour-swapping sort needs exactly $72$ ⁠ swaps.
Step 4 of 5
Open this step
The worst case
Practice · Predict, then look
Question
Quick sorts the shuffled row of 16 blocks in 57 comparisons. Starting order will change to Reversed. What will happen?

Correct answer
- Correct It will make 120 comparisons, as many as bubble sort
Setup, choices and feedback
The Scene at this step
Algorithm
Quickfixed
List size
16 blocksfixed
Starting order
Shuffled
Show how it grows
Blocks
Choices
- Correct It will make 120 comparisons, as many as bubble sort
- Wrong It will make fewer than 57, because a reversed row is more orderly
  Misconception: Thinks quicksort is always the fastest sort, whatever the starting row.
  Feedback from the catalogue
  Quicksort is fast on average, on a shuffled row. The version here always takes the last block as its pivot, and on a sorted or reversed row that block is the tallest or the shortest: each partition removes only one block, and the sort makes $\dfrac{n(n-1)}{2}$ ⁠ comparisons, as many as bubble sort. Real library sorts pick a random or median pivot to avoid this.
- Wrong About the same, because quicksort is always fast
  Misconception: Thinks quicksort is always the fastest sort, whatever the starting row.
  Feedback from the catalogue
  Quicksort is fast on average, on a shuffled row. The version here always takes the last block as its pivot, and on a sorted or reversed row that block is the tallest or the shortest: each partition removes only one block, and the sort makes $\dfrac{n(n-1)}{2}$ ⁠ comparisons, as many as bubble sort. Real library sorts pick a random or median pivot to avoid this.
Once the prediction is locked in, the Scene changes
Starting order
Reversed
The Scene then shows: 120 · Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
$\dfrac{16 \times 15}{2} = 120$ ⁠. The pivot is the last block, and in a reversed row it is the shortest: the partition leaves all the rest on one side, and so on again and again. That is this sort’s worst case.

Worked solution
1. Quicksort picks a pivot and splits the rest into blocks shorter and taller than it; each block is compared with the pivot once.
2. In a reversed row the pivot, the last block, is the shortest, so the partition removes only one block: $15$ ⁠ comparisons, then $14$ ⁠, then $13$ ⁠…
3. In all, $15 + 14 + \cdots + 1 = 120$ ⁠.
In a shuffled row the pivot usually lands near the middle, and the partitions balance.
Step 5 of 5
Open this step
Choosing a method
Practice · Reach the target
Question
Thirty-two blocks, Shuffled. Bubble sort needs 451 comparisons here. Choose the Algorithm that sorts this row in the fewest comparisons, and press Check.

Goal
- 121 ± 0.5
  At the start of the step: 451
Setup, choices and feedback
The Scene at this step
Algorithm
Bubble
List size
32 blocksfixed
Starting order
Shuffledfixed
Show how it grows
Blocks
Read from the Scene at
Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons
One setting that reaches it
Algorithm
Merge
Feedback for a right answer
Merge, with 121 comparisons. Quicksort is very close, 126, and insertion needs 255. On a shuffled row the two methods that split into halves win.

Feedback for a wrong answer
Not yet: one algorithm makes fewer comparisons.

Hint
Try all four algorithms, and read the comparisons on the plaque when each sort finishes.

Worked solution
1. Bubble and insertion sort make about $\dfrac{n^2}{4}$ ⁠ to $\dfrac{n^2}{2}$ ⁠ comparisons on a shuffled row: here 451 and 255.
2. Merge sort and quicksort split into halves, and make about $n \log_2 n = 32 \times 5 = 160$ ⁠ comparisons or fewer.
3. Measure both: merge 121, quick 126.
The gap between those two is small and depends on the row; the gap between them and bubble sort grows with the list.

Lesson 3 of 4 · About 20 minutes

Searching and halving

Two ways to find a name in a list: check them one by one, or open the middle and throw half away. Why binary search needs a sorted list, and how the base-two logarithm counts the halvings it needs.

Open the lesson

The 5 steps and their answers

Step 1 of 5
Open this step
Linear search
Practice · Calculate
Question
In an unsorted list of 1000 names you look for one name, checking them one by one from the start: a linear search. In the worst case, how many names do you have to check?

Correct answer
1000 ± 0.01
Setup, choices and feedback
The Scene at this step
Growth per step
2 ×fixed
Steps
1
Ordinary scale / Log scale
Ordinary scale
Accepted within
± 0.01
A fixed value in the question
Wrong answers it recognises
- 500 ± 0.01
  Misconception: Mixes up the worst case with the average case: gives half the list as the most a linear search can take.
  Feedback from the catalogue
  The worst case asks for the most the algorithm might have to do. In a linear search of a list of 1000 names, the one you want may be last, or not on the list at all, and then you check all 1000. 500 is the average when the name is on the list, in a random place.
- 10 ± 0.01
  Misconception: Thinks binary search works on any list, sorted or not.
  Feedback from the catalogue
  Binary search opens the middle and throws half the list away, and that is allowed only when the list is sorted: if the name in the middle comes after the one you want, the whole half beyond it does too. In an unsorted list the name could be anywhere, and all that is left is to check them one by one. That is why you sort once, to search fast many times.
Feedback for a right answer
All 1000: the name may be the last, or not on the list at all, and then you know only after the last name. The work grows linearly: twice the list, twice the work.

Worked solution
1. The worst case is the input that makes the algorithm work hardest.
2. For a linear search, that is when the name is last on the list or missing from it.
3. Then you check every name: 1000.
If you answered $500$ ⁠, you gave the average when the name is on the list in a random place. If you answered $10$ ⁠, you thought of binary search, which works only on a sorted list.
Step 2 of 5
Open this step
Binary search
Practice · Choose
Question
Binary search opens the list in the middle, checks whether the name there comes before or after the one you want, and throws away the half the name cannot be in. What must be true of the list?

Correct answer
- Correct It is sorted
Setup, choices and feedback
The Scene at this step
Growth per step
2 ×fixed
Steps
1
Ordinary scale / Log scale
Ordinary scale
Choices
Shown in a random order.
- Correct It is sorted
- Wrong Nothing: it works on any list
  Misconception: Thinks binary search works on any list, sorted or not.
  Feedback from the catalogue
  Binary search opens the middle and throws half the list away, and that is allowed only when the list is sorted: if the name in the middle comes after the one you want, the whole half beyond it does too. In an unsorted list the name could be anywhere, and all that is left is to check them one by one. That is why you sort once, to search fast many times.
- Wrong Its length is a power of 2
  Feedback
  A length that is a power of 2 makes the arithmetic neat, but is not needed: when the halves are unequal you round the middle, at the cost of at most one more step.
- Wrong It is short
  Feedback
  It is on long lists that binary search wins by the most.
Feedback for a right answer
Only in a sorted list does the name in the middle tell you anything about the half beyond it. In a dictionary, if you open at “M” looking for “K”, everything after “M” is ruled out.

Worked solution
1. You throw half away because you know the name is not there.
2. You know that only if every name in that half comes after the one in the middle, which is true only of a sorted list.
3. In an unsorted list nothing can be thrown away, and you are left with a linear search.
Step 3 of 5
Open this step
How many halvings
Practice · Reach the target
Question
On the board each step doubles the stack; binary search goes the same way backwards, and halves. Change Steps until the last column reaches 1024, and press Check. That is the number of halvings that shrink 1024 names to one.

Goal
- 1024 ± 0.5
  At the start of the step: 2
Setup, choices and feedback
The Scene at this step
Growth per step
2 ×fixed
Steps
1
Ordinary scale / Log scale
Ordinary scale
Read from the Scene at
Growth: the last column, g^n/nodes/board/outputs/growthValue
One setting that reaches it
Steps
10
Feedback for a right answer
Ten steps: $2^{10} = 1024$ ⁠. So binary search in 1024 sorted names finds any name in at most ten checks, instead of up to 1024 by linear search. $\log_2 1024 = 10$ ⁠.

Feedback for a wrong answer
Not yet. Look at the number on top of the last column.

Hint
$2^5 = 32$ ⁠. How many more steps to $1024$ ⁠?

Worked solution
1. Each halving shrinks the list by 2; each step on the board grows it by 2.
2. The number of halvings from 1024 down to 1 is the number of doublings from 1 up to 1024: $2^k = 1024$ ⁠.
3. $2^{10} = 1024$ ⁠, so $k = \log_2 1024 = 10$ ⁠.
Step 4 of 5
Open this step
A list twice as long
Practice · Predict, then look
Question
In 1024 sorted names binary search needs ten checks. How many will it need in 2048 names, twice as many?

Correct answer
- Correct 11
Setup, choices and feedback
The Scene at this step
Growth per step
2 ×fixed
Steps
10fixed
Ordinary scale / Log scale
Ordinary scale
Choices
- Correct 11
- Wrong 20
  Misconception: Thinks doubling the list doubles the number of steps a binary search takes.
  Feedback from the catalogue
  Each step of a binary search halves the list. A list twice as long needs only one extra halving to get back to the old size, so the number of steps goes up by one: 1024 names take 10 steps, and 2048 take 11. That is the logarithm’s property: $\log_2 (2n) = \log_2 n + 1$ ⁠.
- Wrong Still 10
  Feedback
  Ten halvings shrink 2048 only down to 2 names; one more is needed.
Once the prediction is locked in, the Scene changes
Steps
11fixed
The Scene then shows: 2048 · Growth: the last column, g^n/nodes/board/outputs/growthValue
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
11: the first halving takes 2048 down to 1024, and ten more from there. Doubling the list adds one check. That is what makes binary search so fast on huge lists.

Worked solution
1. $2048 = 2 \times 1024 = 2^{11}$ ⁠.
2. After one halving 1024 names are left, and from there $10$ ⁠ more are needed.
3. In all $\log_2 2048 = 11$ ⁠.
In general $\log_2 (2n) = \log_2 n + 1$ ⁠: multiplying inside the logarithm is adding outside it.
Step 5 of 5
Open this step
A million
Practice · Calculate
Question
A sorted phone book of a million names. At most how many checks does binary search need? (Hint: $2^{10} = 1024$ ⁠, nearly a thousand.)

Correct answer
20 ± 0.5
Setup, choices and feedback
The Scene at this step
Growth per step
2 ×fixed
Steps
10
Ordinary scale / Log scale
Log scale
Accepted within
± 0.5
A fixed value in the question
Wrong answers it recognises
- 6 ± 0.5
  Misconception: Counts halvings with powers of ten, taking about 6 steps for a million because a million is 10⁶.
  Feedback from the catalogue
  Binary search halves, so you count powers of 2, not of 10. A million is $10^6$ ⁠, but each step shrinks the list by two, not by ten. $2^{10} = 1024$ ⁠, so ten halvings shrink it about a thousand times, and twenty halvings about a million times: $2^{20} = 1{,}048{,}576$ ⁠. So $\log_2 10^6 \approx 20$ ⁠.
- 500000 ± 0.5
  Misconception: Mixes up the worst case with the average case: gives half the list as the most a linear search can take.
  Feedback
  500000 is the average of a linear search. Binary search throws away half the list with every check.
Feedback for a right answer
20: $2^{20} = 1024 \times 1024 = 1{,}048{,}576$ ⁠, a little over a million. A linear search would need up to a million checks; binary search needs twenty.

Hint
How many times must 1024 be multiplied by itself?

Worked solution
1. A million is about a thousand times a thousand.
2. Each thousand is about $2^{10}$ ⁠, so a million is about $2^{10} \times 2^{10} = 2^{20}$ ⁠.
3. $2^{19} = 524{,}288$ ⁠ is less than a million and $2^{20} = 1{,}048{,}576$ ⁠ is more, so twenty halvings are enough and nineteen are not.
If you answered $6$ ⁠, you counted powers of 10; each step shrinks by 2, not by 10.

Lesson 4 of 4 · About 25 minutes

Growth rates and big-O

What happens to the work when the list doubles: bubble sort grows like the square of the length, and merge sort only a little faster than the length itself. The graph that compares them, big-O notation, and why a good algorithm beats a fast computer.

Open the lesson

The 6 steps and their answers

Step 1 of 6
Open this step
Doubling the list
Practice · Predict, then look
Question
Bubble sort on a Reversed row of 16 blocks makes 120 comparisons. List size will double to 32. How many comparisons will there be?

Correct answer
- Correct About four times: 496
Setup, choices and feedback
The Scene at this step
Algorithm
Bubblefixed
List size
16 blocks
Starting order
Reversedfixed
Show how it grows
Blocks
Choices
- Correct About four times: 496
- Wrong Twice: 240
  Misconception: Expects every algorithm's work to double when its input doubles.
  Feedback from the catalogue
  Only work that grows linearly, like a linear search, doubles when the list doubles. Bubble sort compares pairs, and the number of pairs grows about like $n^2$ ⁠: a list twice as long takes about four times the comparisons, 120 for sixteen blocks and 496 for thirty-two. That is why an algorithm that looks quick on ten items can grind to a halt on a million.
- Wrong 136: sixteen more blocks
  Misconception: Expects every algorithm's work to double when its input doubles.
  Feedback from the catalogue
  Only work that grows linearly, like a linear search, doubles when the list doubles. Bubble sort compares pairs, and the number of pairs grows about like $n^2$ ⁠: a list twice as long takes about four times the comparisons, 120 for sixteen blocks and 496 for thirty-two. That is why an algorithm that looks quick on ten items can grind to a halt on a million.
Once the prediction is locked in, the Scene changes
List size
32 blocks
The Scene then shows: 496 · Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
$\dfrac{32 \times 31}{2} = 496$ ⁠, about four times 120. A list twice as long has twice the blocks, and each of them has to meet twice as many others.

Worked solution
1. On a reversed row bubble sort compares every pair: $\dfrac{n(n-1)}{2}$ ⁠.
2. For $n = 32$ ⁠: $\dfrac{32 \times 31}{2} = 496$ ⁠.
3. The ratio: $\dfrac{496}{120} \approx 4.1$ ⁠.
When the work grows like $n^2$ ⁠, doubling $n$ ⁠ multiplies it by $2^2 = 4$ ⁠.
Step 2 of 6
Open this step
Doubling with merge sort
Practice · Predict, then look
Question
Now Merge: on a Reversed row of 16 blocks it makes 32 comparisons. What will happen when List size doubles to 32?

Correct answer
- Correct A little over twice as many
Setup, choices and feedback
The Scene at this step
Algorithm
Mergefixed
List size
16 blocks
Starting order
Reversedfixed
Show how it grows
Blocks
Choices
- Correct A little over twice as many
- Wrong About four times, as with bubble sort
  Feedback
  Merge sort does not compare every pair. It merges level by level, and the number of levels, $\log_2 n$ ⁠, goes up by only one when the list doubles.
- Wrong Exactly twice
  Feedback
  Close, but there is also one more level of merging: not $2 \times 32 = 64$ ⁠ but a little more.
Once the prediction is locked in, the Scene changes
List size
32 blocks
The Scene then shows: 80 · Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
80, two and a half times. On a reversed row merge sort makes $\dfrac{n}{2} \log_2 n$ ⁠ comparisons: $8 \times 4 = 32$ ⁠, then $16 \times 5 = 80$ ⁠. Growth like $n \log n$ ⁠ is only a little faster than linear growth.

Worked solution
1. Merge sort goes through $\log_2 n$ ⁠ levels, and on a reversed row each level costs $\dfrac{n}{2}$ ⁠ comparisons.
2. For $n = 16$ ⁠: $\log_2 16 = 4$ ⁠ levels of $8$ ⁠, that is $32$ ⁠.
3. For $n = 32$ ⁠: $\log_2 32 = 5$ ⁠ levels of $16$ ⁠, that is $80$ ⁠.
Doubling doubles each level and adds one level: $\dfrac{80}{32} = 2.5$ ⁠.
Step 3 of 6
Open this step
The growth board
Practice · Calculate
Question
Show how it grows is on Growth: the orange ribbon is $\dfrac{n(n-1)}{2}$ ⁠, the number of pairs. Bubble sort on a Reversed row of 64 blocks compares every pair once. How many comparisons is that?

Correct answer
2016 ± 0.01
Setup, choices and feedback
The Scene at this step
Algorithm
Bubblefixed
List size
64 blocksfixed
Starting order
Reversedfixed
Show how it grows
Growthfixed
Accepted within
± 0.01
Computed from the Scene at this step’s setting
N(n − 1)/2: comparing every pair once, the orange ribbon/nodes/sort/outputs/everyPair
Wrong answers it recognises
- 4096 ± 0.01
  Misconception: Counts n × n comparisons for comparing every pair, counting each pair twice and a block against itself.
  Feedback from the catalogue
  To compare every pair once, each block meets each of the other $n - 1$ ⁠, which is $n(n-1)$ ⁠, but that counts every pair twice, once from each side. So the number of pairs is $\dfrac{n(n-1)}{2}$ ⁠: for eight blocks $\dfrac{8 \times 7}{2} = 28$ ⁠, not $64$ ⁠. It grows like $n^2$ ⁠, but it is not $n^2$ ⁠ itself.
- 4032 ± 0.01
  Misconception: Counts n × n comparisons for comparing every pair, counting each pair twice and a block against itself.
  Feedback from the catalogue
  To compare every pair once, each block meets each of the other $n - 1$ ⁠, which is $n(n-1)$ ⁠, but that counts every pair twice, once from each side. So the number of pairs is $\dfrac{n(n-1)}{2}$ ⁠: for eight blocks $\dfrac{8 \times 7}{2} = 28$ ⁠, not $64$ ⁠. It grows like $n^2$ ⁠, but it is not $n^2$ ⁠ itself.
Feedback for a right answer
$\dfrac{64 \times 63}{2} = 2016$ ⁠. By contrast $n \log_2 n = 64 \times 6 = 384$ ⁠, and the blue ribbon is already far below the orange.

Hint
$\dfrac{n(n-1)}{2}$ ⁠ with $n = 64$ ⁠.

Worked solution
1. Each of the $64$ ⁠ blocks meets $63$ ⁠ others: $64 \times 63 = 4032$ ⁠.
2. That counts every pair twice, so divide by $2$ ⁠.
3. $\dfrac{4032}{2} = 2016$ ⁠.
If you answered $4096$ ⁠, you worked out $64^2$ ⁠: that counts a block against itself and every pair twice.
Step 4 of 6
Open this step
Big-O
Practice · Choose
Question
On a reversed row bubble sort makes $\tfrac12 n^2 - \tfrac12 n$ ⁠ comparisons. How is that written in big-O notation?

Correct answer
- Correct $O(n^2)$ ⁠
Setup, choices and feedback
The Scene at this step
Algorithm
Bubble
List size
64 blocks
Starting order
Shuffled
Show how it grows
Growth
Choices
Shown in a random order.
- Correct $O(n^2)$ ⁠
- Wrong $O(\tfrac12 n^2 - \tfrac12 n)$ ⁠
  Misconception: Keeps the constant factors and smaller terms inside big-O, writing O(½n² − ½n) instead of O(n²).
  Feedback from the catalogue
  Big-O describes only how the work grows as $n$ ⁠ grows, so constant factors and slower-growing terms are dropped. In $\tfrac12 n^2 - \tfrac12 n$ ⁠ the $n^2$ ⁠ term dominates: multiply $n$ ⁠ by ten and the work grows about a hundredfold, whatever the coefficient. So bubble sort is $O(n^2)$ ⁠.
- Wrong $O(\tfrac12 n^2)$ ⁠
  Misconception: Keeps the constant factors and smaller terms inside big-O, writing O(½n² − ½n) instead of O(n²).
  Feedback from the catalogue
  Big-O describes only how the work grows as $n$ ⁠ grows, so constant factors and slower-growing terms are dropped. In $\tfrac12 n^2 - \tfrac12 n$ ⁠ the $n^2$ ⁠ term dominates: multiply $n$ ⁠ by ten and the work grows about a hundredfold, whatever the coefficient. So bubble sort is $O(n^2)$ ⁠.
- Wrong $O(n)$ ⁠
  Misconception: Expects every algorithm's work to double when its input doubles.
  Feedback from the catalogue
  Only work that grows linearly, like a linear search, doubles when the list doubles. Bubble sort compares pairs, and the number of pairs grows about like $n^2$ ⁠: a list twice as long takes about four times the comparisons, 120 for sixteen blocks and 496 for thirty-two. That is why an algorithm that looks quick on ten items can grind to a halt on a million.
Feedback for a right answer
$O(n^2)$ ⁠: the fastest-growing term is $n^2$ ⁠, and the factor $\tfrac12$ ⁠ does not change the shape of the growth. Big-O answers one question: what happens to the work as $n$ ⁠ grows.

Worked solution
1. Keep the fastest-growing term: $\tfrac12 n^2$ ⁠. The term $\tfrac12 n$ ⁠ is negligible for long lists; for $n = 1000$ ⁠ it is under a tenth of a per cent.
2. Drop the factor $\tfrac12$ ⁠: it does not change how many times the work grows when $n$ ⁠ doubles.
3. The result: $O(n^2)$ ⁠.
Merge sort, by contrast, is $O(n \log n)$ ⁠, and binary search $O(\log n)$ ⁠.
Step 5 of 6
Open this step
Finding the size
Practice · Reach the target
Question
Bubble, Reversed. Change List size until the sort makes exactly 190 comparisons, and press Check.

Goal
- 190 ± 0.5
  At the start of the step: 120
Setup, choices and feedback
The Scene at this step
Algorithm
Bubblefixed
List size
16 blocks
Starting order
Reversedfixed
Show how it grows
Blocks
Read from the Scene at
Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons
One setting that reaches it
List size
20 blocks
Feedback for a right answer
20 blocks: $\dfrac{20 \times 19}{2} = 190$ ⁠.

Feedback for a wrong answer
Not yet. Work out $\dfrac{n(n-1)}{2}$ ⁠ for the size you chose.

Hint
$n(n-1) = 380$ ⁠: look for two consecutive numbers whose product is $380$ ⁠.

Worked solution
1. You want $\dfrac{n(n-1)}{2} = 190$ ⁠, that is $n(n-1) = 380$ ⁠.
2. $n^2$ ⁠ is close to $380$ ⁠, so $n$ ⁠ is close to $\sqrt{380} \approx 19.5$ ⁠.
3. Check: $20 \times 19 = 380$ ⁠. So $n = 20$ ⁠.
Step 6 of 6
Open this step
A better algorithm
Practice · Choose
Question
A million shuffled items have to be sorted. Computer A does $10^9$ ⁠ comparisons a second and runs bubble sort, about $5 \times 10^{11}$ ⁠ comparisons. Computer B is a hundred times slower, $10^7$ ⁠ comparisons a second, and runs merge sort, about $2 \times 10^7$ ⁠ comparisons. Which finishes first?

Correct answer
- Correct Computer B, with merge sort
Setup, choices and feedback
The Scene at this step
Algorithm
Merge
List size
64 blocks
Starting order
Shuffled
Show how it grows
Growth
Choices
Shown in a random order.
- Correct Computer B, with merge sort
- Wrong Computer A, because it is a hundred times faster
  Misconception: Thinks a faster computer makes up for a slow algorithm.
  Feedback from the catalogue
  A computer a hundred times faster cuts the time a hundredfold, and no more. A better algorithm can cut it thousands of times, and the gap grows with the list. To sort a million items, bubble sort makes about $5 \times 10^{11}$ ⁠ comparisons, and merge sort about $2 \times 10^7$ ⁠: twenty-five thousand times fewer. No hardware upgrade closes a gap like that.
- Wrong About the same time
  Misconception: Thinks a faster computer makes up for a slow algorithm.
  Feedback from the catalogue
  A computer a hundred times faster cuts the time a hundredfold, and no more. A better algorithm can cut it thousands of times, and the gap grows with the list. To sort a million items, bubble sort makes about $5 \times 10^{11}$ ⁠ comparisons, and merge sort about $2 \times 10^7$ ⁠: twenty-five thousand times fewer. No hardware upgrade closes a gap like that.
Feedback for a right answer
Computer B, in about 2 s; computer A needs about 500 s, over eight minutes. A better algorithm beat a computer a hundred times faster, and on a longer list the gap only grows.

Hint
Divide each computer’s comparisons by the comparisons it does a second.

Worked solution
1. Computer A: $\dfrac{5 \times 10^{11}}{10^9} = 500$ ⁠ seconds.
2. Computer B: $\dfrac{2 \times 10^7}{10^7} = 2$ ⁠ seconds.
3. Computer B finishes $250$ ⁠ times sooner.
The computer’s speed multiplies the time by a fixed number; the algorithm decides how the time grows with the list.

Across the unit · 12 misconceptions

Misconception catalogue

Each common mistake this unit recognises, in a few words. Open one for what the learner reads when an answer matches it, and where it is asked.

Index

The steps of an algorithm

Exact steps

Question

Correct answer

The Scene at this step

Choices

Worked solution

One pass

Question

Correct answer

The Scene at this step

Hint

Worked solution

The tallest drifts to the end

Question

Correct answer

The Scene at this step

Choices

Worked solution

Every pair

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint

Worked solution

Counting swaps

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint

Worked solution

Stopping early

Question

Correct answer

The Scene at this step

Once the prediction is locked in, the Scene changes

Worked solution

Comparing sorts

Four ways

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Worked solution

Merge sort

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint

Worked solution

Swaps and inverted pairs

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Worked solution

The worst case

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Worked solution

Choosing a method

Question

Goal

The Scene at this step

One setting that reaches it

Hint

Worked solution

Searching and halving

Linear search

Question

Correct answer

The Scene at this step