Computer Science · Grade 11

Active learning ideas

Algorithmic Efficiency and Big O Notation

Active learning works for algorithmic efficiency because students need hands-on experience to grasp how operations scale beyond small examples. Timing races and graphing tasks make abstract growth rates concrete, while games build quick recognition of patterns in nested loops and recursion.

• Ontario Curriculum Expectations
• CS.HS.A.5

• 30–50 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Collaborative Problem-Solving
• 50 min · Small Groups

Collaborative Problem-Solving: Algorithm Timing Race

Students implement linear search and binary search in Python, test on sorted arrays from size 10 to 10,000, and log execution times. Groups plot data points to visualize O(n) versus O(log n) growth. Conclude with a class share-out on patterns observed.

Explain the purpose of Big O notation in comparing algorithms.

Facilitation Tip

During the Algorithm Timing Race, circulate to ensure groups run tests on input sizes that clearly show scaling differences, like 100, 1,000, and 10,000 elements.

What to look for

Present students with short pseudocode snippets or descriptions of algorithms (e.g., iterating through a list once, nested loops processing a 2D array). Ask them to write down the Big O notation for each and justify their answer by identifying the dominant operation.

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Activity 02

• Simulation Game
• 30 min · Pairs

Simulation Game: Big O Code Match

Prepare cards with code snippets and complexity notations. Pairs match snippets to O(n), O(n log n), or O(n²), justifying choices by counting operations. Review as whole class, tallying scores for fun competition.

Analyze how different operations contribute to an algorithm's time complexity.

Facilitation Tip

In Big O Code Match, remind students to focus on iteration counts and nesting before matching notation to snippets.

What to look for

Pose the question: 'Imagine you have two sorting algorithms, one with O(n log n) and another with O(n^2). Which would you choose to sort 100 items, and which for 1 million items? Explain your reasoning using the concept of growth rates.'

• Apply
• Analyze
• Evaluate
• Create
• Social Awareness
• Decision-Making

Activity 03

• Timeline Challenge
• 40 min · Small Groups

Timeline Challenge: Optimization Relay

Teams receive a task like finding duplicates in a list. Each member proposes an algorithm, times it on sample data, and passes to next for Big O analysis. Groups present best solution with complexity justification.

Differentiate between O(n), O(n log n), and O(n^2) complexities with examples.

Facilitation Tip

For the Optimization Relay, pause after each round to have groups share their key change and the new Big O.

What to look for

Provide students with a simple algorithm (e.g., finding the maximum element in an unsorted array). Ask them to: 1. State its Big O complexity. 2. Briefly explain why it has that complexity by describing the operations involved.

• Remember
• Understand
• Analyze
• Self-Management
• Relationship Skills

Activity 04

• Concept Mapping
• 35 min · Individual

Graphing: Complexity Curves

Individuals use spreadsheets or Python to simulate loop counts for O(1), O(n), O(n²). Plot curves for n=1 to 1000. Share graphs in pairs to compare shapes and predict large-n behavior.

Explain the purpose of Big O notation in comparing algorithms.

Facilitation Tip

When graphing Complexity Curves, ask leading questions like 'Where does the quadratic curve cross the linear one?' to push deeper analysis.

What to look for

Present students with short pseudocode snippets or descriptions of algorithms (e.g., iterating through a list once, nested loops processing a 2D array). Ask them to write down the Big O notation for each and justify their answer by identifying the dominant operation.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

A few notes on teaching this unit

Experienced teachers approach this topic by starting with real timing data so students feel the gap between O(n) and O(n²) before introducing notation. Avoid rushing to formulas; instead, use code tracing and peer discussion to build intuition. Research shows that students retain concepts better when they first experience inefficiency through their own measurements.

Successful learning looks like students accurately predicting Big O, explaining dominant operations in code, and choosing algorithms based on growth rates rather than speed on a single test. They should justify decisions with traces, graphs, or timing data.

---

Watch Out for These Misconceptions

• During Algorithm Timing Race, watch for students interpreting runtime in seconds as the measure of efficiency rather than comparing how runtimes grow with input size.

  Prompt groups to plot their recorded times on axes labeled 'Input Size' and 'Runtime' and observe the curve shapes, then ask them to explain why a straight line or steep curve matters more than the exact seconds.

• During Big O Code Match, watch for students assuming any loop counts as O(n) regardless of nesting or control flow.

  Have students annotate each snippet with iteration counts for each loop, then match the total operations to Big O before selecting notation, emphasizing multiplicative effects.

• During Complexity Curves, watch for students concluding O(log n) grows faster than O(n) when n is small in their plots.

  Ask them to extend their graphs to n = 100,000 and discuss why the logarithmic curve flattens while the linear one climbs sharply, using their plotted data as evidence.

---

Methods used in this brief

• Collaborative Problem-Solving
• Simulation Game
• Timeline Challenge
• Concept Mapping