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.

• 11th Grade
• Computer Science
• 4 activities
• 20 min–40 min

Learning Objectives

1. Classify algorithms into common Big O complexity classes, including O(1), O(n), O(log n), and O(n^2).
2. Analyze the time complexity of simple algorithms by tracing their execution and counting operations.
3. Compare the efficiency of two different algorithms designed to solve the same problem, justifying the choice based on Big O notation.
4. Predict how the runtime of an algorithm will change as the input size increases, using its Big O classification.
5. Explain the difference between worst-case, average-case, and best-case scenarios in algorithm analysis.

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.

Prepare & details

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.

Setup: Flexible space for group stations

Materials: Role cards with goals/resources, Game currency or tokens, Round tracker

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

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.

Prepare & details

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.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

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

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.

Prepare & details

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.

Setup: Wall space or tables arranged around room perimeter

Materials: Large paper/poster boards, Markers, Sticky notes for feedback

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

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.

Prepare & details

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.

Setup: Standard classroom seating; students turn to a neighbor

Materials: Discussion prompt (projected or printed), Optional: recording sheet for pairs

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

Teaching This Topic

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.

What to Expect

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

Common Misconception

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

What to Teach Instead

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.

Common Misconception

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.

What to Teach Instead

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.

Common Misconception

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

What to Teach Instead

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.

Assessment Ideas

Quick Check

After the Human Algorithm Race, provide pseudocode for two algorithms (e.g., finding the max in an array, duplicate checking with nested loops). Ask students to identify the Big O notation for each and justify their answer by referring to the dominant operation they counted during the race.

Discussion Prompt

During the Think-Pair-Share Best Choice Scenarios, have students debate the trade-offs between an O(n log n) sorting algorithm and an O(n²) algorithm for a dataset of 100,000 items. Assess their reasoning by asking them to consider factors beyond Big O, such as memory usage and code readability.

Exit Ticket

After the Runtime Charting Lab, ask students to write down one algorithm they have written or encountered, classify its time complexity, and explain why they chose that classification based on the operation counts they recorded in the lab.

Extensions & Scaffolding

• Challenge: Ask students to write an O(1) algorithm that works for any input size, then explain why constants and lower-order terms matter in practice.
• Scaffolding: Provide partially completed Big O classification cards with some operations already counted to help students focus on the growth rate.
• Deeper: Have students design a hybrid algorithm that switches between O(n log n) and O(n²) based on input size, then justify the threshold.

Key Vocabulary

Big O Notation	A mathematical notation used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it describes the upper bound of an algorithm's runtime or space complexity.
Time Complexity	A measure of how long an algorithm takes to run as a function of the size of the input. It is typically expressed using Big O notation.
Space Complexity	A measure of the amount of memory an algorithm requires to run as a function of the size of the input. It is also typically expressed using Big O notation.
Logarithmic Time (O(log n))	An algorithm whose runtime grows logarithmically with the input size. This is very efficient, as the time increases slowly even for large inputs, common in divide-and-conquer algorithms like binary search.
Linear Time (O(n))	An algorithm whose runtime grows directly proportional to the input size. Doubling the input size roughly doubles the runtime, seen in algorithms that iterate through a list once.
Quadratic Time (O(n^2))	An algorithm whose runtime grows proportionally to the square of the input size. This is less efficient, often occurring with nested loops that iterate over the same input.