Computer Science · Grade 12

Active learning ideas

Big O Notation: Fundamentals

Big O notation can feel abstract until students see it in action. Active learning turns the invisible scaling of algorithms into visible patterns they measure and debate. When students time loops, sort snippets, and race graphs, they connect symbols like O(n) to real performance changes.

• Ontario Curriculum Expectations
• CS.AA.2
• CS.DSAA.14

• 20–45 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Case Study Analysis
• 30 min · Pairs

Pairs: Loop Timing Challenge

Pairs write pseudocode for single and nested loops, then simulate runs by counting operations for increasing n values from 10 to 1000. They record times on charts and predict Big O classes. Discuss patterns as a class.

Why is the worst-case scenario often more important than the average case in software safety?

Facilitation Tip

Before the Loop Timing Challenge, provide identical starter code on different devices so timing differences come from loop structure, not hardware.

What to look for

Present students with 3-4 code snippets, each containing a simple loop or nested loop structure. Ask students to write down the Big O notation for each snippet and briefly justify their answer by identifying the dominant operation.

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management

Activity 02

• Case Study Analysis
• 25 min · Small Groups

Small Groups: Code Snippet Sort

Provide cards with algorithm snippets like linear search or bubble sort. Groups classify each by Big O, justify choices, and test with sample inputs. Share one insight per group.

Explain the concept of asymptotic analysis and its relevance to Big O notation.

Facilitation Tip

During Code Snippet Sort, set a 3-minute timer per group to force quick analysis and prevent over-explaining easy cases.

What to look for

On an index card, ask students to write: 1) One reason why worst-case analysis is important for software safety. 2) An example of an algorithm with O(n) time complexity and a brief description of what it does.

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management

Activity 03

• Case Study Analysis
• 45 min · Whole Class

Whole Class: Runtime Graph Race

Class runs simple algorithms on shared computers or paper simulations for n=100 to 10,000. Plot collective data on a shared graph to visualize O(n) vs O(n^2). Vote on steepest curves.

Analyze the Big O complexity of simple iterative algorithms.

Facilitation Tip

For the Runtime Graph Race, pre-plot axes on poster paper so students focus on curve shape, not axis scaling.

What to look for

Facilitate a class discussion using the prompt: 'Imagine you are designing a system to recommend movies to millions of users. Why would choosing an algorithm with O(log n) complexity over one with O(n^2) complexity be critical for the success of this recommendation service?'

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management

Activity 04

• Case Study Analysis
• 20 min · Individual

Individual: Worst-Case Hunt

Students analyze given functions, identify worst-case inputs, and compute Big O. Swap papers for peer review, then revise based on feedback.

Why is the worst-case scenario often more important than the average case in software safety?

Facilitation Tip

In Worst-Case Hunt, give each student a sealed envelope with worst-case input data to ensure fairness and surprise.

What to look for

Present students with 3-4 code snippets, each containing a simple loop or nested loop structure. Ask students to write down the Big O notation for each snippet and briefly justify their answer by identifying the dominant operation.

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management

A few notes on teaching this unit

Teachers often rush to definitions before students feel the pain of slow code. Start with a live demo of a quadratic algorithm on large data, then ask students to time linear loops. Use the phrase 'as n grows' repeatedly to anchor discussions in scaling rather than speed. Avoid diving into Big Theta or Omega early; stick to Big O’s upper-bound role until students own worst-case thinking.

By the end, students should confidently classify code snippets, explain why constants drop out, and defend worst-case choices in design scenarios. Success looks like students pointing to graphs and saying, 'This O(n log n) sort will stay under control even when n doubles.'

---

Watch Out for These Misconceptions

• During the Loop Timing Challenge, watch for students treating timing results as exact Big O values.

  After students record times, ask each pair to compute ratios between sizes (e.g., time at n=1000 vs n=2000) and relate these ratios to expected growth patterns like 2:1 for O(n) or 4:1 for O(n^2).

• During the Code Snippet Sort, watch for students counting every loop iteration as part of Big O.

  Have groups physically cross out constants and lower-order terms on their printed snippets, then justify why those terms are irrelevant when n is large.

• During the Worst-Case Hunt, watch for students assuming average inputs are sufficient for analysis.

  Ask students to swap their worst-case envelopes mid-activity and rerun the algorithm to see how average-case assumptions break under adversarial data.

---

Methods used in this brief

• Case Study Analysis