Reading Runtime Growth

Overview

Students investigate why algorithm efficiency matters by revisiting Big O notation, analysing recursive Fibonacci in Python, and comparing it with iterative and dynamic-programming solutions. They use timing evidence to interpret growth across input sizes, rather than treating one benchmark as a complete performance judgement.

Learning intentions

• WALT explain what Big O notation communicates about runtime growth.
• WALT explain why constant factors are dropped in asymptotic analysis.
• WALT implement and compare recursive, iterative and dynamic-programming algorithms.
• WALT use profiling evidence to justify an optimisation decision.

Success criteria

• I can identify the dominant term in a runtime expression and simplify it using Big O notation.
• I can explain why (O(2n)) and (O(n)) are treated as the same growth class.
• I can predict why naïve recursive Fibonacci becomes impractical.
• I can use repeated timings and input-size comparisons to support a conclusion about efficiency.

Curriculum links

• Computer science concepts: explain algorithm complexity and use evidence to evaluate algorithm performance, supporting the computer science concept focus of AS91898.
• Complex programming techniques: implement, test, trace and refine recursive and dynamic-programming solutions, supporting AS91906.
• Technology practice: develop computational solutions through informed testing, evaluation and refinement.
• NZ Curriculum capabilities: thinking; managing self; using language, symbols and texts; participating and contributing.

Lesson structure (60 minutes)

1. 0–7 min · Hook and retrieval. Display the opening runtime-growth question and ask, “Which is faster: an algorithm taking (n) steps or one taking (1,000n) steps?” Students complete the first section of the algorithm efficiency investigation sheet from memory: define Big O, rank (O(1)), (O(\log n)), (O(n)), (O(n\log n)), (O(n^2)), and identify one real-world reason efficiency matters.

2. 7–17 min · Explicit teaching. Use the Big O explanation slides to recap that Big O describes how resource use grows as input size increases, not an exact stopwatch time. Model (T(n)=3n^2+20n+7): the (n^2) term dominates for large (n), so the classification is (O(n^2)). Explicitly discuss dropping constants: (O(2n)), (O(100n)) and (O(n)) have different practical speeds but the same long-run growth pattern; asymptotic analysis ignores constant factors to compare scalability across machines and implementations. Students annotate the worksheet and answer: “When might a constant factor still matter?”

3. 17–27 min · Teacher modelling: recursion. Open the Fibonacci trace and code slides and live-code or display:

def fib_recursive(n):
 if n <= 1:
 return n
 return fib_recursive(n - 1) + fib_recursive(n - 2)

print(fib_recursive(10))

Trace fib_recursive(5) with students, highlighting repeated calls such as fib(3) and fib(2). Explain that the branching produces approximately exponential growth, commonly described as (O(2^n)), while the call stack uses (O(n)) space. Students predict which values will become slow and record one reason repeated work occurs.

4. 27–42 min · Paired coding investigation. In pairs, students use the worksheet task and starter file to run the recursive version, then implement and test:

def fib_iterative(n):
 a, b = 0, 1
 for _ in range(n):
 a, b = b, a + b
 return a

def fib_dp(n):
 values =
 for i in range(2, n + 1):
 values.append(values[i - 1] + values[i - 2])
 return values[n]

Students verify outputs against one another before timing. They should test a safe range such as `` for recursion and a larger range for the efficient methods. They record correctness, runtime, input size and observations in the timing table and analysis questions. Circulate and ask: “What must remain constant for this comparison to be fair?” and “What pattern would convince you that growth is exponential rather than merely slow?”

5. 42–51 min · Evidence and optimisation. Model a simple repeated timing function from the profiling and evidence slides:

from time import perf_counter

def average_time(function, n, repeats=5):
 start = perf_counter()
 for _ in range(repeats):
 function(n)
 return (perf_counter() - start) / repeats

Students time each algorithm several times, use matching inputs, and compare how runtime changes when n increases. Discuss why one result can be noisy: background processes, timer resolution, caching and small input sizes. Students produce one evidence-based claim using the structure: “When input changes from ___ to ___, ___ changes by approximately ___, suggesting ___.”

6. 51–56 min · Formative discussion and misconceptions. Pairs compare claims, then respond to the slides’ prompts. Address likely misconceptions: Big O is not an exact time; dropping constants does not mean constants are irrelevant in practice; recursion is not automatically inefficient; memoisation removes repeated subproblems but uses memory; and a single benchmark cannot establish an asymptotic class. Students correct one misconception in their notes.

7. 56–60 min · Exit ticket. Students complete the final section of the four-question exit ticket independently: classify (5n+4), explain constant-factor removal, state why naïve Fibonacci is inefficient, and identify what timing evidence would support an optimisation. Collect responses for next-lesson grouping.

Resources

• the algorithm efficiency slide deck
• the algorithm efficiency investigation sheet
• Python 3 environment or school-approved online IDE
• Devices for 25 students, preferably one per student
• Projector and teacher coding environment
• Timing table and graphing tool, such as a spreadsheet
• Whiteboard and pens

Assessment

• Listen for accurate explanations during retrieval, recursion tracing and paired discussion; ask selected students to justify, not merely state, a Big O classification.
• Check code output, fair-test decisions, repeated measurements and the quality of students’ growth interpretations during the investigation.
• Use exit tickets to identify whether students confuse exact runtime with asymptotic growth, or fail to connect memoisation with removal of repeated work.

Differentiation

• Support: provide a partially completed trace tree, function templates, a Big O reference strip on the worksheet, and sentence starters such as “The dominant term is…” and “This suggests…”.
• Support students with additional learning needs by pairing strategically, chunking the coding task, allowing typed rather than handwritten analysis, and providing teacher-prepared timing data if setup or processing time becomes a barrier.
• EAL support: pre-teach “growth”, “dominant”, “constant factor”, “repeated subproblem” and “evidence”, with diagrams and plain-language definitions.
• Extension: students add a memoised recursive version using a dictionary or functools.lru_cache, then compare its time and space trade-offs with the iterative solution and justify which implementation is most appropriate for a stated context.