Computer Science · 11th Grade

Active learning ideas

Big O Notation Fundamentals

Big O notation transforms abstract symbols into a shared language that students can use to compare algorithms. When students move from writing code to analyzing its efficiency, active learning helps them connect the mathematical concept to the concrete steps of an algorithm.

• Common Core State Standards
• CSTA: 3B-AP-11

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

Activity 01

• Simulation Game
• 35 min · Small Groups

Simulation Game: The Human Algorithm Race

Assign groups to physically simulate O(1), O(n), O(log n), and O(n²) operations using index cards of increasing quantities (10, 20, 40). Groups record their operation counts at each size and plot results, then compare the growth curves to the formal Big O classifications.

Analyze how Big O notation quantifies the efficiency of an algorithm.

Facilitation Tip

During the Human Algorithm Race, assign roles like 'input generator' and 'operation counter' to make the relationship between steps and growth visible to the whole class.

What to look for

Provide students with pseudocode for 2-3 simple algorithms (e.g., finding the max in an array, checking for duplicates with nested loops). Ask them to identify the Big O notation for each algorithm and justify their answer by explaining the dominant operation.

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

Activity 02

• Problem-Based Learning
• 40 min · Pairs

Data Collection Lab: Runtime Charting

Pairs time their own code for loops and algorithms at multiple input sizes (n=100, 1000, 10000) and plot the results on a shared class graph. Groups then classify each plot by its Big O shape and compare their classifications.

Differentiate between common Big O complexities (O(1), O(n), O(n^2), O(log n)).

Facilitation Tip

In the Runtime Charting Lab, have students graph both operation counts and measured times on the same axes to demonstrate why Big O focuses on growth, not absolute values.

What to look for

Pose the scenario: 'You have two sorting algorithms. Algorithm A is O(n log n) and very concise. Algorithm B is O(n^2) but much easier to understand and debug. For a dataset of 100,000 items, which would you choose and why? Consider factors beyond just the theoretical Big O classification.'

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

Activity 03

• Gallery Walk
• 30 min · Small Groups

Gallery Walk: Big O Classification Cards

Post stations around the room with pseudocode snippets representing different Big O complexities. Groups rotate, classify each snippet, and leave their reasoning as a sticky note. Discrepancies between groups become the basis for whole-class discussion.

Predict the performance of an algorithm as input size scales based on its Big O classification.

Facilitation Tip

During the Gallery Walk, place classification cards with algorithm snippets in visible locations so students can move, compare, and annotate them collaboratively.

What to look for

Ask students to write down one algorithm they have previously written or encountered. Then, have them classify its time complexity using Big O notation and briefly explain why they chose that classification.

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

Activity 04

• Think-Pair-Share
• 20 min · Pairs

Think-Pair-Share: Best Choice Scenarios

Present three real scenarios (searching a contact list, querying a database, sorting a small config file) with different size constraints. Pairs decide which Big O complexity is acceptable for each scenario and justify their choice before sharing with the class.

Analyze how Big O notation quantifies the efficiency of an algorithm.

Facilitation Tip

For the Think-Pair-Share scenarios, provide real code examples students have written before to ground the discussion in familiar contexts.

What to look for

Provide students with pseudocode for 2-3 simple algorithms (e.g., finding the max in an array, checking for duplicates with nested loops). Ask them to identify the Big O notation for each algorithm and justify their answer by explaining the dominant operation.

• Understand
• Apply
• Analyze
• Self-Awareness
• Relationship Skills

A few notes on teaching this unit

Teachers should start with algorithms students already know, like linear search or duplicate checking, before introducing new ones. Focus on the dominant operation and avoid early overemphasis on constants or lower-order terms. Research shows that students grasp complexity classes more deeply when they collect their own data rather than relying on textbook examples.

By the end of these activities, students will confidently explain how an algorithm’s operations grow with input size and justify their classification using Big O notation. They will also recognize that real-world performance depends on more than just the complexity class.

---

Watch Out for These Misconceptions

• During the Runtime Charting Lab, watch for students who record actual time in seconds and assume that time equals Big O complexity.

  Redirect students to count the number of operations in their algorithm first, then graph operation counts against input size. Ask them to compare the shape of the graph to Big O classes before considering clock time.

• During the Think-Pair-Share Best Choice Scenarios, watch for students who assert that O(log n) is always faster than O(n) regardless of input size.

  Have students test both algorithms with small inputs (e.g., n=10) using the same codebase and runtime setup from the lab. Ask them to compare the actual times and discuss why constants and overhead matter for small n.

• During the Gallery Walk Classification Cards, watch for students who assume Big O only applies to sorting and searching.

  Include cards with non-sorting examples like a function that checks if a number is prime or a loop that renders UI elements. Ask students to classify these and explain how the dominant operation scales with input.

---

Methods used in this brief

• Simulation Game
• Problem-Based Learning
• Gallery Walk
• Think-Pair-Share