B2.4 · HL Python

Programming algorithms: reading & review

Connect each topic to your textbook, lesson and a question you can answer independently.

Class progress as of 17 September: linear search and Big O are covered; binary search is next. Sorting and HL recursion follow later. Use these questions for revision.

Explore the animations → Download the student review → Back to B2.4 →

What belongs in this unit

Page numbers below are printed textbook pages, not the PDF viewer’s counter. The review includes worked examples, original questions R1–R4 and answers for checking your work afterwards.

IB objective	Textbook	Show understanding	Class progress
B2.4.1 Efficiency and scalability	pp. 358–361	Explain time and auxiliary space, describe growth and justify algorithm choice. Review: R1	Big O lesson covered · review in progress Open lesson →
B2.4.2 Linear and binary search	pp. 361–365	Construct and trace both searches; test absent targets and list boundaries. Review: R2	Linear search covered · binary search next Open lesson →
B2.4.3 Bubble and selection sort	pp. 365–369	Construct and trace both sorts, then compare time and extra memory for the stated implementation. Review: R3	Planned Open lesson →
B2.4.4 · HL Recursion and its applications	pp. 370–371; applications 373–377	Explain base cases, progress, stack memory and applications including quicksort, fractals and tree traversal. Review: R4	Planned · teaching date to be set Open lesson →
B2.4.5 · HL Constructing and tracing recursion	pp. 371–377 · selected examples	Write and trace simple non-branching recursive functions. The guide limits construction and tracing here to this scope. Review: R4	Planned · teaching date to be set Open lesson →

Read these examples carefully

Binary search: page 364

For the inclusive loop shown in the book, initialize upper = len(numbers) - 1. A list with seven items has indices 0 to 6; index 7 is outside it. Test an absent target larger than the last item as well as a successful search.

Memory: page 361

The summation example uses O(1) extra working memory, or O(n) total memory when the supplied list is included. Read the explanation of auxiliary space below →

HL recursion

Understand how quicksort, fractals and tree traversal use recursion. For B2.4.5 construction and tracing, practise simple non-branching functions with at most one recursive call in each activation.

Space complexity: what are we counting?

Auxiliary space means the extra working memory an algorithm needs, beyond the input it has already been given. Think of it as scratch space: counters, a running total, new lists and the memory used by active function calls.

In the summation example on textbook page 361, numbers is the supplied input list. The algorithm keeps a running total in sum and uses a fixed number of extra variables. Whether the list has 10 items or 10,000, it still needs only those few variables: O(1) auxiliary space.

The textbook’s O(n) space statement counts the input list too: storing n items takes memory that grows with n. That is total space, including the input. Both descriptions can be correct; they count different things.

A larger value in sum does not mean we keep more totals. For this classroom analysis, we treat each number as one fixed-size value. Creating a new copy of all n items, or saving every intermediate total, would instead need O(n) auxiliary space.

When explaining an answer, state your convention: “O(1) auxiliary space; O(n) total space including the input list.” Time is a separate question: visiting every item still takes O(n) time.

Practise explaining your answer

Read the objective and its textbook section.
Work through the example, then attempt the linked review question on paper.
Check the answer and identify the exact step or idea you missed.
Repeat with different data and explain why your answer works.

Original classroom practice uses marks to show what an answer needs. The IB FAQ clarifies that Big O assessment asks you to describe growth, without formal calculations; pseudocode is not required for Paper 2. A raw score is not automatically an IB grade from 1 to 7.