The shape of the lesson
By the end of the lesson, learners can
- Fair comparisons: Timing two programs with a stopwatch is not a fair test: the result depends on the processor, the language, the compiler and whatever else is running.
- Big O notation: In the lab, compare the two searches, then the two sorts, as the list grows.
- Space complexity: Memory is the second criterion.
- Criteria: time taken (operations as n grows) and memory used (extra storage).
- Simplify: keep the dominant term, drop constants: 4n2 + 9n is O(n2).
- Order: O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n).
- Predict: scale n by k and the time scales by k for O(n), k2 for O(n2).
One picture every idea returns to
Algorithms that perform the same task are compared by the time taken (the number of basic steps, such as comparisons) and the memory used, as the number of data items n grows. Big O notation gives the order of growth in the worst case: keep only the dominant term and drop constants, so 3n2 + 5n + 2 steps is O(n2). Time complexity ranks O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n). Space complexity uses the same notation for extra memory: an in-place sort is O(1), a copy of the data is O(n).
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, Count the growth.. Two algorithms that do the same job can be compared by the time they take and the memory they use. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: Fair comparisons | Timing two programs with a stopwatch is not a fair test: the result depends on the processor, the language, the compiler and whatever else is running. Model the worked example Count the steps on the board, one line at a time. Your turn: A loop runs FOR i ← 1 TO n and its body contains three assignments and no other loop. How many assignments are executed for n = 50, and what is its time complexity? | Whole class, then pairs |
| 13 to 21 min | Teach and check: Big O notation | In the lab, compare the two searches, then the two sorts, as the list grows. Project tab 5 of the lab (Comparing algorithms) and let a student drive it while the class predicts. Model the worked example Predict the run time on the board, one line at a time. Your turn: Give the Big O time complexity of an algorithm that makes 4n + 7 log 2 n + 20 comparisons, and of one that makes 0.01n 3 + 500n comparisons. | Pairs |
| 21 to 30 min | Teach and check: Space complexity | Memory is the second criterion. Model the worked example Choose an algorithm on the board, one line at a time. Your turn: Why is a binary search tree built from data that arrives in sorted order a poor choice for searching? | Jigsaw |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 20 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in Space complexity, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Jigsaw
Split the content into expert pieces. Expert groups master one piece each, then regroup so every home team has one expert per piece, and each expert teaches their piece to the team.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| "Algorithm A is faster because it took 0.3 seconds" earns nothing. | Compare the number of operations as n increases, or the Big O order. |
| O(log n) does not mean "fewer than n" for every n, and O(n 2) does not give an exact count. | Big O describes how the work grows; for very small n a "worse" algorithm can still be quicker. |
| Do not confuse the two criteria. "It uses less memory" is a space argument; "it makes fewer comparisons" is a time argument. | Say which one you mean and link it to n. |
Comparing algorithms: Big O notation: worksheet
6 questions, 20 marks. Written in the style of the papers; no past paper question is reproduced.
Explain what is meant by Big O notation and why it is used to compare algorithms.
State the time complexity of each algorithm in Big O notation: (a) binary search (b) bubble sort (c) linear search (d) popping an item from a stack.
An O(n) algorithm and an O(n2) algorithm each take 0.4 seconds to process 500 records. Estimate how long each takes for 2500 records. Show your working.
State how many times Total ← Total + i * j is executed when n = 8, and give the time complexity:
FOR i ← 1 TO n
FOR j ← 1 TO 4
Total ← Total + i * j
NEXT j
NEXT iA program stores 100 000 product codes. Compare keeping them in an unsorted array and searching with a linear search, with keeping them in a sorted array and searching with a binary search. Refer to time and space complexity.
A recursive function calls itself n times before reaching its base case, and each call does a fixed amount of work. State its time complexity and its space complexity, and explain the space complexity.
Answer key and marking notes
- It describes the order of growth of an algorithm's time (or space) requirement as the number of data items n increases.
- It usually describes the worst case and ignores constants and lower-order terms.
- It allows algorithms to be compared independently of hardware and programming language / shows how well each scales to large data.
- (a) O(log n).
- (b) O(n2).
- (c) O(n).
- (d) O(1).
- 2500 / 500 = 5 times the data.
- O(n): 0.4 × 5 = 2 seconds.
- O(n2): 0.4 × 52 = 0.4 × 25 = 10 seconds.
- The inner loop always runs 4 times, whatever n is.
- 8 × 4 = 32 times.
- 4n grows linearly with n, so O(n) (the inner loop is not over the data).
- Linear search is O(n): up to 100 000 comparisons; binary search is O(log n): at most 17 comparisons.
- Both searches need only O(1) extra memory (a few variables).
- The sorted array must be kept in order, so inserting a new code costs time (items must be shifted, O(n)).
- If searches are much more frequent than inserts, the sorted array with binary search is better.
- Time: O(n).
- Space: O(n).
- Each call that has not yet returned keeps a stack frame (return address, parameters, local variables) on the call stack, so up to n frames are held at once.
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
An algorithm makes 2n log2 n + 50n + 7 comparisons for n items. What is its time complexity in Big O notation?
- AO(n log n)
- BO(n)
- CO(2n log n)
- DO(n2)
Count ← 0
FOR i ← 1 TO n
FOR j ← 1 TO i
Count ← Count + 1
NEXT j
NEXT iWhat is the value of Count when n = 8, and what is the time complexity?- A36, O(n2)
- B64, O(n2)
- C36, O(n)
- D8, O(n)
An O(n2) algorithm takes 3 seconds to process 500 items. Estimate its time for 1500 items.
- A27 seconds
- B9 seconds
- C81 seconds
- DAbout 10.6 seconds
FUNCTION Sum(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 0
ELSE
RETURN n + Sum(n - 1)
ENDIF
ENDFUNCTIONWhat is the space complexity of Sum(n)?- AO(n)
- BO(1)
- CO(log n)
- DO(n2)
Steps ← 0
WHILE n > 1
n ← n DIV 2
Steps ← Steps + 1
ENDWHILE
OUTPUT StepsWhat is output when n starts at 1000, and what is the time complexity of the loop?- A9, O(log n)
- B10, O(log n)
- C500, O(n)
- D9, O(n)
Algorithm A makes 100n log2 n operations and algorithm B makes n2 operations. Which statement is correct?
- AB makes fewer operations at n = 512, but A makes fewer at n = 4096
- BA makes fewer operations for every n, because O(n log n) grows more slowly
- CB makes fewer operations for every n, because it has no constant of 100
- DA makes fewer operations at n = 512, but B makes fewer at n = 4096
Quiz key
For large n the n log n term dominates 50n and 7, and the constant 2 is dropped, giving O(n log n). O(n) picks the 50n term because its constant is larger, but constants do not decide growth. O(2n log n) keeps the constant, and O(n2) overstates the growth: there is no n2 term.
1 + 2 + ... + 8 = 8 × 9 / 2 = 36, which is n(n + 1)/2 = 0.5n2 + 0.5n, so the order is O(n2). 64 assumes the inner loop always runs 8 times. 36 with O(n) gets the count right but misreads the growth: halving n2 does not make it linear. 8 counts only the outer loop.
1500 is 3 times 500, so the time is multiplied by 32 = 9: 3 × 9 = 27 seconds. 9 seconds treats the growth as linear, 81 seconds multiplies by 34, and about 10.6 seconds is the estimate for an O(n log n) algorithm, not an O(n2) one.
Sum(n) calls Sum(n − 1), and so on down to Sum(0), so n + 1 stack frames are on the call stack at the deepest point: the extra memory grows in proportion to n, O(n). O(1) would be true of a loop with one running total, O(log n) would need the parameter to halve each call, and O(n2) would need each frame to hold n items.
n takes the values 500, 250, 125, 62, 31, 15, 7, 3, 1: nine halvings, and then n > 1 is FALSE. Because n is halved each time the number of iterations is about log2 n, so O(log n). 10 rounds log2 1000 up instead of counting the DIV steps, 500 counts only the first halving as if it were a linear loop, and O(n) would need n to fall by a fixed amount each time.
At n = 512: A = 100 × 512 × 9 = 460 800 and B = 262 144, so B is smaller. At n = 4096: A = 4 915 200 and B = 16 777 216, so A is smaller. Big O describes growth: A eventually wins, but its large constant means B is quicker for small n. That rules out both 'every n' statements, and the last option has the two cases the wrong way round.
What to project
The student lesson embeds these tabs. Open them full screen on the projector; every slider has a drag handle on the stage.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.