Homework · Assigned

Read pages 358–361: Big O notation

Due 18 Sept 2026 · 4 pages

Review the Big O lesson by reading pages 358–361 in Computer Science for the IB Diploma by Baumgarten, Ganea & Turland. Next: binary search.

Your tasks

Task 1

Read pages 358–361

Use the printed page numbers in your CS textbook. This reading covers Big O notation. Read all four pages, including the examples.

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.

Assignment checklist

Complete the reading on printed pages 358–361.

This is a reading assignment. No additional written submission is required for this task.

If you need help

Use the page numbers printed in the textbook, which may differ from the page counter in a PDF viewer. If a passage is unclear, bring the question to class.

Revisit the lesson Open the student handout (PDF)