Teacher Guide: Algorithms & Complexity

Student page: Algorithms & Complexity IB Syllabus: B2.4 (SL + HL) Suggested timing: 3–4 periods (SL); add 1–2 for HL recursion/quicksort

Lesson Plans
Differentiation
1. Supporting weaker students
2. Extending stronger students
Teaching Sequence
Common Student Mistakes
IB Paper 2 Exam Tips

Lesson Plans

SL Period 1: Big O + Linear Search (90 min)

Phase	Time	Activity	Notes
Warm-up	10 min	“500 unsorted papers vs sorted phonebook” — two search strategies	Natural language before terminology
Teach	15 min	Big O notation — the doubling question, growth rate table	Build table live on board
Teach	15 min	Linear search — “Guess My Card” activity, trace table	Trace before code
Practice	35 min	Linear search trace exercises + code from student page
Wrap-up	15 min	Quick Code Check MCQs on Big O + linear search

SL Period 2: Binary Search (90 min)

Phase	Time	Activity	Notes
Warm-up	10 min	“Guess My Number” 1-100 — teacher demonstrates binary search live	At most 7 guesses
Teach	25 min	Binary search algorithm, trace table (found + not found cases), sorted prerequisite	Multiple trace examples
Practice	40 min	Binary search trace exercises + code from student page
Wrap-up	15 min	“What if the array is unsorted?” — silent failure demo

SL Period 3: Bubble Sort (90 min)

Phase	Time	Activity	Notes
Warm-up	10 min	Physical card sort — 5 students with number cards	Unplugged bubble sort
Teach	20 min	Bubble sort algorithm, pass-by-pass trace format, nested loop → O(n²)	IB exam format: show array after each PASS
Practice	45 min	Bubble sort trace exercises + code from student page
Wrap-up	15 min	“How many comparisons for n=100?” → 10,000. Connect to Big O

SL Period 4: Selection Sort + Comparison (90 min)

Phase	Time	Activity
Warm-up	10 min	“Is there a smarter way?” — propose finding minimum and swapping once
Teach	20 min	Selection sort algorithm, comparison table (bubble vs selection), trace
Practice	35 min	Selection sort trace exercises + code from student page
Wrap-up	25 min	Algorithm comparison activity: match algorithm → Big O → use case

HL Period 5: Recursion (90 min)

Phase	Time	Activity	Notes
Warm-up	10 min	Call stack from methods unit — “remember frames being pushed and popped?”	Connect to B2.3.4
Teach	25 min	Recursive factorial — call stack visualisation on board, base case, StackOverflowError demo
Practice	40 min	Recursive exercises: factorial trace, Fibonacci trace, count repeated calls
Wrap-up	15 min	“When is recursion better than a loop?” — elegance vs efficiency discussion

HL Period 6: Quicksort (90 min)

Phase	Time	Activity
Warm-up	10 min	“Split 1000 names into two groups of 500, sort each” — divide and conquer
Teach	25 min	Quicksort: pivot, partition, recursive calls. Trace on small array (6-8 elements)
Practice	40 min	Quicksort trace exercises, worst case analysis, comparison with O(n²) sorts
Wrap-up	15 min	Big O summary: all algorithms on one chart. “Which would you choose and when?”

Differentiation

Supporting weaker students

Strategy	When to use	Example
Physical sort first	Can’t follow code	Card sort activity before any code — understand the algorithm physically
Trace template	Can’t set up trace tables	Pre-printed templates with column headers for binary search (low, high, mid, arr[mid], decision)
One algorithm at a time	Overwhelmed by comparisons	Master linear search fully before introducing binary search
Visual Big O chart	Can’t remember growth rates	Poster: O(1) < O(log n) < O(n) < O(n²) with graphs
Sorting pass worksheets	Can’t show pass-by-pass	Pre-printed array boxes — fill in values after each pass

Extending stronger students

Strategy	When to use	Example
Bubble sort optimisation	Finishes sort early	“Add an `isSorted` flag — if no swaps in a pass, stop early. What’s the best case now?”
Algorithm comparison project	After all SL algorithms	Time each algorithm on arrays of size 100, 1000, 10000 — graph the results
Merge sort preview	HL students after quicksort	“There’s another divide-and-conquer sort that’s always O(n log n)…”
Real-world application	After binary search	“Phone contacts app uses binary search. What must be true about the list?”
Fibonacci memoisation	After recursion	“Can you avoid recalculating fibonacci(2) multiple times?” — introduce memoisation
Worst case analysis	After quicksort	“Design an input that makes quicksort perform at its worst”

Teaching Sequence

Opening: two kinds of search

Opening scenario — two strategies:

Ask: “You need to find a specific name in a pile of 500 unsorted papers vs. a sorted phonebook. Describe how you would do each.” Students describe:

Unsorted: check one by one from the start
Phonebook: open to the middle, decide which half, repeat

This is linear vs binary search — described in natural language before any code or terminology. Write the strategies on the board. Ask: “In the worst case, how many papers might you check in each scenario?” Students calculate: 500 vs ~9 (log₂ 500 ≈ 9). This makes the case for Big O before it is formally introduced.

Big O notation (B2.4.1)

The doubling question:

After the opening scenario, ask: “What if the pile doubles from 500 to 1000 papers?” For linear search: twice as many checks. For binary search: one extra check. This is the most intuitive way to explain O(n) vs O(log n) without any mathematics.

Build the table on the board live:

Algorithm	n = 100	n = 1000	n = 1,000,000
O(1)	1	1	1
O(log n)	~7	~10	~20
O(n)	100	1,000	1,000,000
O(n²)	10,000	1,000,000	10¹²

The O(n²) row always generates a reaction. The point lands without a formal proof.

Common misconception to address: O(log n) confuses students because they often think log₂ of a large number is large. Compute a few: log₂(1024) = 10, log₂(1,000,000) ≈ 20. This makes O(log n) feel impressively efficient.

Linear search (B2.4.2)

“Guess My Card” activity:

Shuffle a standard deck face-down. Ask a volunteer to flip cards one at a time looking for the Ace of Spades. After a few flips, ask the class: “In the worst case, how many cards might they need to flip?” (52 — the Ace could be the last card.) “What is the average?” (~26.) This is O(n) made physical and memorable.

Trace before code:

Before writing any code, complete a trace table together as a class. Choose a small array and a target. Fill in i, arr[i], and whether it matches. Only after the trace is complete — and students can articulate the pattern — write the code.

Early exit: Point out the && !found condition. Ask: “Why is this here? What happens without it?” Students should explain: without it, the loop continues even after finding the target. This is efficiency and correctness in the same example.

Binary search (B2.4.3)

“Guess My Number” activity:

Tell a student to think of a number 1–100. You will guess it using at most 7 questions, each answered “higher” or “lower.” Guess 50 first. Demonstrate 2–3 rounds. Ask: “Why do I always guess the midpoint?” Students realise: you eliminate half the remaining possibilities each time.

Then ask: “How many guesses do I need for a number 1–128? 1–1024?” Students calculate: 7 and 10. Connect to log₂(128) = 7, log₂(1024) = 10.

Trace table before code: Binary search is harder to code than to trace. Do the trace table first — multiple examples including a “not found” case. Students who can trace it reliably can write it reliably.

Critical prerequisite — sorted array:

Ask: “What if the array is unsorted?” Run the algorithm mentally on an unsorted example and show how it fails silently — returns -1 even when the element is present. This is a more dangerous failure than a crash, because the program doesn’t report an error.

low = high + 1 to end the loop: The student page uses this instead of break. Explain why: it makes the loop termination condition visible in the condition check, rather than relying on a jump. Both work; this version is easier to trace.

Bubble sort (B2.4.4)

Physical card sort:

Give 5 students each a card with a number (written large). Ask them to stand in a row. Run bubble sort physically: adjacent pairs compare, the taller-numbered person moves right if out of order. After one complete pass, the largest number has “bubbled” to the end.

Ask: “After pass 2, what is guaranteed to be in its final position?” (The second largest.) Students see the invariant physically before seeing it in code.

Key questions during the physical sort:

“How many comparisons were made in that pass?”
“Does the inner loop need to go all the way to the end on pass 2?”
“How many passes do we need in total for 5 elements?”

Connecting nested loops to Big O:

After the physical sort, ask: “The outer loop runs ~n times. The inner loop runs ~n times. How many comparisons total?” Students calculate n × n = n². This is the intuitive derivation of O(n²) — no algebra required.

IB exam format: For exam questions, students must show the entire array state after each pass, not each individual swap. Drill this format during practice. Marking schemes award marks per pass, not per swap.

Selection sort (B2.4.5)

“Smarter way?” contrast:

After completing bubble sort, ask: “Is there a smarter way? Bubble sort swaps a lot of adjacent pairs. Could we find the minimum element and just put it at the front in one swap?” Let students propose this. Confirm: that is exactly selection sort.

Key comparison with bubble sort:

	Bubble	Selection
Swaps per pass	Many (up to n−1)	Exactly one
Comparisons	O(n²)	O(n²)
Best case	O(n) with optimisation	O(n²) always

Ask: “When would you prefer selection sort over bubble sort?” The answer: when swaps are expensive (e.g., moving large objects in memory), because selection sort guarantees only one swap per pass.

HL Only: Recursion (B2.4.6)

Call stack visualisation:

Before writing recursive code, draw the call stack on the board. Each method call is a box pushed on a stack. When a method returns, the box is popped. Trace factorial(4) by drawing and removing boxes — students see the unwinding.

Base case — the critical point:

Ask: “What happens if there is no base case?” Run a recursive method with no base case (or an impossible-to-reach base case) in BlueJ — show the StackOverflowError. The call stack fills up. This makes the base case feel non-optional rather than arbitrary.

Fibonacci inefficiency:

After fibonacci(n) is implemented, trace fibonacci(5) and count how many times fibonacci(2) is called. Students are surprised by the repetition. Ask: “Is this a problem for large n?” This motivates the concept of dynamic programming (beyond syllabus, but good for HL curiosity).

HL Only: Quicksort (B2.4.7)

Divide and conquer concept first:

Ask: “If you need to sort 1000 names, would you rather sort them all at once, or split them into two groups of 500, sort each, and merge?” Students see the appeal of splitting. Quicksort takes this further: it splits AND sorts simultaneously around a pivot.

Worst case discussion:

Ask: “What is the worst input for quicksort if we always choose the last element as pivot?” An already-sorted array — every partition splits into 1 and n-1. Students calculate: n + (n-1) + … + 1 = n(n+1)/2 = O(n²). This makes the worst case concrete and memorable.

Common Student Mistakes

Mistake	Description
Binary search on unsorted data	Silently returns wrong results — does not throw an error
Bubble sort: showing swaps not passes	Exam requires the array state after each PASS
Off-by-one in binary search bounds	`high = arr.length` instead of `arr.length - 1`
Confusing O(n) and O(n²)	Review the doubling question for each
Selection sort: claiming it’s faster than bubble	Both are O(n²) — selection sort makes fewer swaps, not fewer comparisons
Recursion: missing or wrong base case	Leads to infinite recursion and StackOverflowError

IB Paper 2 Exam Tips

Binary search trace format: Show low, high, mid, arr[mid], and the decision (search left/right/found) for every step. Show the final row where the loop terminates.
Bubble sort trace format: Show the full array after each pass. Circle or underline the element that has reached its final position at the end of each pass.
Big O — know four values cold: O(1) constant, O(log n) binary search, O(n) linear search, O(n²) both sorts.
Justify Big O choices — “binary search is O(log n) because each comparison halves the search space” scores more than just writing the notation.
For HL: recursion trace — draw the call stack with push/pop. Show which call is on top at each moment. factorial(3) trace is a very common HL question.
Pre-condition for binary search: A sorted array. Exam questions sometimes ask “what must be true of the array before applying binary search?”