Comparing Algorithmic Complexity

Overview

Year 13 Technology students compare algorithmic complexity, use Big O notation to describe asymptotic growth, simplify expressions by identifying the dominant term, and rank common complexity classes. They are introduced to the distinction between P and NP, including why checking a solution may be easier than finding one and why whether P = NP remains unknown.

Learning intentions

• Understand that Big O describes asymptotic growth as the input size approaches infinity, not exact runtime in seconds.
• Simplify polynomial and logarithmic expressions by retaining the dominant term.
• Compare common complexity classes and explain the basic distinction between P and NP.
• Connect algorithmic efficiency to practical constraints such as time, memory, cost and energy.

Success criteria

• I can explain why Big O focuses on growth as (n) approaches infinity rather than exact runtime.
• I can simplify polynomial/logarithmic expressions to their dominant Big O class.
• I can rank (O(1)), (O(\log n)), (O(n)), (O(n\log n)), (O(n^2)), and (O(n!)) from most to least efficient for large (n).
• I can explain why (P) is a subset of (NP) and why the (P) vs (NP) question matters.

Curriculum links

• Demonstrate understanding of the application of a technical area to a specific field: explain technical ideas, developments, limitations and opportunities related to algorithms in computing and communication.
• Demonstrate understanding of operational parameters in complex and highly complex technological systems: explain how time and resource constraints influence system design and maintenance.
• New Zealand Curriculum Technology: use technological knowledge to understand how technological outcomes are developed, evaluated and used.
• New Zealand Curriculum key competencies: thinking; using language, symbols and texts; managing self; participating and contributing.

Lesson structure (60 minutes)

1. 0–10 min · Warm-up and retrieval. Teacher reminds students that Big O describes asymptotic growth as (n \to \infty), not exact runtime in seconds. Pose: “Which grows faster as (n) becomes very large: (n) or (1000n)?” Establish that both are (O(n)), although constants affect real performance. Students discuss, justify their answer and complete a quick ranking prompt. Formative checkpoint: listen for the distinction between growth class and actual runtime.

2. 10–12 min · Share intentions and criteria. Teacher shares the learning intention and success criteria and clarifies the vocabulary students will use. Students restate one criterion in their own words and identify a personal focus.

3. 12–20 min · Explicit teaching: dominant terms. Teacher models dropping constants and keeping the biggest-growth term: (3n^2+50n+1000=O(n^2)), (3n^2+20n+7=O(n^2)), and (O(2n)=O(100n)=O(n)). Emphasise that constants disappear from the growth class, not from real performance. Students identify the dominant term in teacher examples and justify each answer. Formative checkpoint: use responses to correct confusion between coefficients and exponents.

4. 20–26 min · P vs NP video. Before viewing, teacher asks, “Why might checking a solution be easier than finding one?” Play the video up to 5:51 only. Students record key definitions and one question. After viewing, teacher clarifies that (P) concerns problems solvable in polynomial time, (NP) concerns solutions verifiable in polynomial time, (P \subseteq NP), and whether (P=NP) is unknown. Avoid overstating claims about cryptography. Formative checkpoint: check definitions and address the misconception that NP means “not polynomial.”

5. 26–43 min · Collaborative algorithm efficiency investigation. Teacher provides the first section of the Algorithm Efficiency Investigation slide/worksheet and prompts students to justify rankings and connect complexity to search, sorting, data scale, time, memory, cost or energy. In pairs, students rank (O(1)), (O(\log n)), (O(n)), (O(n\log n)), (O(n^2)), and (O(n!)) from most to least efficient for large (n), then identify one real-world reason efficiency matters. Formative checkpoint: question unsupported rankings using “What happens as (n) becomes very large?”

6. 43–52 min · Guided practice and discussion. Teacher models and then students solve ((3n+5)\to O(n)), ((n^2+100n+\log n)\to O(n^2)), and ((4n\log n+2n)\to O(n\log n)). Include the misconception check that dropping constants does not mean ignoring actual performance, and (n^2) is not always slower than (n) for small inputs. Students explain their reasoning to a partner.

7. 52–57 min · P vs NP consolidation. Teacher facilitates pair-share responses to: (1) What does “polynomial time” mean? (2) Why is checking a proposed solution associated with (NP)? (3) Why is (P\subseteq NP)? (4) Why is (P=NP) still an open problem? Students answer, compare and revise responses. Formative checkpoint: listen for “every P problem can be verified” rather than the incorrect claim that P and NP are known to be equal.

8. 57–60 min · Exit ticket. Teacher collects responses to three prompts: simplify one expression, rank two complexity classes, and write 1–2 sentences explaining why (P\subseteq NP) and why the reverse inclusion remains unknown. Students answer independently.

Resources

• Big O and P vs NP slide deck
• Algorithm Efficiency Investigation slide/worksheet
• Video: https://www.youtube.com/watch?v=OY41QYPI8cw (play only to 5:51)
• Whiteboard and markers
• Timer
• Optional calculators or spreadsheet software

Key vocabulary: asymptotic growth, input size, dominant term, constant factor, logarithmic, polynomial time, verification, solvable, complexity class, (P), (NP), (P\subseteq NP), (P=NP).

Assessment

Formative assessment:

• Warm-up explanations reveal whether students distinguish asymptotic growth from exact runtime.
• Dominant-term examples check whether students drop lower-order terms and recognise that constants still affect real performance.
• Pair rankings and worksheet justifications check comparison of complexity classes and practical implications.
• P vs NP questioning checks accurate use of solvable, verifiable, polynomial time and subset notation.
• Exit tickets provide evidence for reteaching or extension.

Likely misconceptions to address:

• Big O is not an exact number of seconds; it describes growth for large (n).
• Dropping constants for Big O does not mean constants have no practical effect.
• (n^2) is not always slower than (n) for small inputs.
• NP does not mean “not polynomial.”
• (P\subseteq NP) is established, but whether (P=NP) is unknown; do not claim that cryptography depends straightforwardly on its resolution.

Concise answer guide:

• (n) and (1000n): both are (O(n)); (1000n) may take longer in practice.
• (3n^2+50n+1000): (O(n^2)); (3n^2+20n+7): (O(n^2)); (2n,100n,n): (O(n)).
• Efficiency ranking, most to least efficient for large (n): (O(1), O(\log n), O(n), O(n\log n), O(n^2), O(n!)).
• (3n+5\to O(n)); (n^2+100n+\log n\to O(n^2)); (4n\log n+2n\to O(n\log n)).
• (P\subseteq NP) because a polynomial-time solution can also be checked in polynomial time. The reverse inclusion is unknown because no proof that (P=NP) or (P\ne NP) has been found.

Differentiation

• Students needing support: provide a completed example, a dominant-term colour-coding guide, a visual growth-rate table, and sentence starters such as “As (n) becomes large…” and “The dominant term is…”. Allow calculator or spreadsheet use and pair rehearsal before sharing.
• Provide a ranking scaffold that first compares (O(n)) and (O(n^2)), then adds (O(1)), (O(\log n)), (O(n\log n)) and (O(n!)). Include a vocabulary box defining solvable, verifiable, polynomial and subset.
• Extension: ask students to compare operation counts for selected input sizes, explain why constants matter in practice despite being omitted from Big O, or explain why a problem may be easy to verify without a known efficient solving method.
• EAL support: pre-teach key vocabulary, use paired discussion and visual notation, and read worksheet instructions aloud where needed.