B2.4 · Algorithm efficiency · Covered

Big O notation

Review Big O notation with the class handout and textbook pages 358–361. Compare how time and auxiliary space grow with input size.

17 Sept 2026 · 55 minutes

For this lesson

Open student handout (PDF) Class activities ↓ Try the example in Python → Homework · due 18 Sept 2026

Animations: Constant growth · O(1)Linear growth · O(n)Logarithmic growth · O(log n)Quadratic growth · O(n²)Auxiliary space

Python · step by step

Linear growth · O(n)

Example

Watch the number of marked operations as input size changes.

Select Play or Next line to follow Python execution.

Python implementation

The highlight marks the next line to execute. Values show the state before that line.

1visits = []23def growth_linear(n):4    for i in range(n):5        visits.append(i)6    return len(visits)

Speed

Execution progress

visits is an instrumentation list used only to show work. Do not count this display logging when judging the underlying algorithm’s auxiliary space. We count append events, not every Python operation.

Python · step by step

Auxiliary space

Example

Compare a running total with a growing copy of the input.

Select Play or Next line to follow Python execution.

Python implementation

The highlight marks the next line to execute. Values show the state before that line.

1def auxiliary_space(items, copy_input):2    total = 03    working = []4    for value in items:5        total = total + value6        if copy_input:7            working.append(value)8    return total

Speed

Execution progress

The supplied list is input space. total and value occupy a fixed number of slots in our classroom model. The copy grows to n elements. Without the copy: O(1) auxiliary space; with it: O(n). Both scans take O(n) time.

By the end of this lesson

Distinguish input size from the number of operations.
Compare common growth patterns without relying on a particular computer’s speed.
Explain why constant factors do not change the Big O class.

Use these activities to review the topic at your own pace. Timings are approximate.

Review the lesson

01 · 5 minutes

Start with a comparison

Compare looking up the first list item with checking every item. What changes when the list doubles in length?

02 · 15 minutes

Count operations

Count the work in a single loop over n values, two consecutive loops, and two nested loops. Try n = 4 and n = 8 before generalizing.

03 · 15 minutes

Describe growth

Connect constant, logarithmic, linear and quadratic growth to the algorithms you have met. Distinguish growth rate from measured execution time.

04 · 15 minutes

Apply the notation

Compare linear search with binary search. State the case being considered and explain the role of sorted input. Discuss auxiliary space separately from time.

05 · 5 minutes

Explain

Explain why doing two full passes over a list still has linear growth rather than quadratic growth.

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.

Before you leave

Exit question

If an input doubles, what happens to the work in a linear algorithm and a quadratic algorithm?

Homework for this topic

Due 18 Sept 2026 · 4 pages · Assigned

Read pages 358–361: Big O notation

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