Computer Science · Grade 11

Active learning ideas

Analyzing Time and Space Complexity

Active learning helps students grasp the abstract concept of time and space complexity by making it concrete and measurable. By timing searches, tracking memory usage, and predicting outcomes, students see how Big O notation translates into real performance differences that matter in programming decisions.

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

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

Activity 01

• Problem-Based Learning
• 45 min · Pairs

Pair Programming: Search Timing

Students in pairs implement linear and binary search in Python. They test on sorted arrays from size 100 to 1,000,000, averaging runtimes over 20 trials. Pairs graph results and infer Big O notations from slopes.

Evaluate the trade-offs between an algorithm's time complexity and its space complexity.

Facilitation Tip

During Pair Programming: Search Timing, set a minimum input size of 10,000 elements to ensure differences between O(n) and O(n^2) are measurable and meaningful.

What to look for

Provide students with 2-3 short code snippets (e.g., a loop, a nested loop, a recursive function call). Ask them to write down the Big O time complexity for each snippet and a brief justification. For example: 'This code has a time complexity of O(n) because it iterates through the input array once.'

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

Activity 02

• Problem-Based Learning
• 50 min · Small Groups

Small Groups: Sort Trade-offs

Groups code bubble sort and merge sort, measuring time and space with timeit and sys.getsizeof. They input sizes up to 10,000, discuss trade-offs, and present findings on why one suits certain scenarios.

Analyze the factors that determine an algorithm's space complexity.

Facilitation Tip

For Small Groups: Sort Trade-offs, provide a table for students to record iterations, swaps, and memory usage for each sorting algorithm to compare time and space trade-offs directly.

What to look for

Pose the following scenario: 'Imagine you are designing an application that needs to sort a list of 1 million user IDs. One algorithm has a worst-case time complexity of O(n^2) but uses very little extra memory. Another has an average-case time complexity of O(n log n) but requires an auxiliary array of the same size as the input. Which would you choose and why? Discuss the trade-offs.'

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

Activity 03

• Problem-Based Learning
• 35 min · Whole Class

Whole Class: Complexity Predictions

Display pseudocode for algorithms. Class votes on Big O predictions, then codes and tests as a group using shared Jupyter notebook. Debrief mismatches between theory and practice.

Predict how an algorithm's performance will scale with increasing input size based on its Big O notation.

Facilitation Tip

In Whole Class: Complexity Predictions, use a think-pair-share structure to allow students to test their predictions immediately with provided code snippets on unsorted and sorted arrays.

What to look for

Ask students to define 'space complexity' in their own words and provide one example of an algorithm or data structure that typically has a high space complexity (e.g., recursion, adjacency list for a dense graph) and explain why.

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

Activity 04

• Problem-Based Learning
• 25 min · Individual

Individual: Space Analysis Worksheet

Students trace space usage for recursive algorithms like mergesort on paper. They calculate stack depth and auxiliary space, then verify with code on small inputs.

Evaluate the trade-offs between an algorithm's time complexity and its space complexity.

What to look for

Provide students with 2-3 short code snippets (e.g., a loop, a nested loop, a recursive function call). Ask them to write down the Big O time complexity for each snippet and a brief justification. For example: 'This code has a time complexity of O(n) because it iterates through the input array once.'

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

A few notes on teaching this unit

Teach this topic by grounding Big O in hands-on measurement rather than abstract symbols. Students benefit from seeing how constants and lower-order terms disappear as input size grows, so emphasize large datasets and consistent testing conditions. Avoid overgeneralizing; instead, use specific examples to build intuition about when to prioritize time versus space complexity in design decisions.

Students will confidently classify algorithms using Big O notation, justify their choices with data, and explain trade-offs between time and space efficiency. They will use evidence from activities to support their reasoning about algorithm selection for different scenarios.

---

Watch Out for These Misconceptions

• During Pair Programming: Search Timing, watch for students measuring runtime in seconds and concluding that a faster algorithm is always better regardless of input size.

  After Pair Programming: Search Timing, ask students to graph their timing results for increasing input sizes, then point out how O(n^2) starts slower but grows much faster than O(n) as n increases, making it less scalable.

• During Small Groups: Sort Trade-offs, watch for students assuming lower memory usage always outweighs higher time complexity.

  During the activity, guide students to calculate the total cost by multiplying time by memory usage for each sort, highlighting that O(n log n) algorithms often balance these factors more effectively for large datasets.

• During Whole Class: Complexity Predictions, watch for students applying Big O notation without checking whether the data is sorted before using binary search.

  After Whole Class: Complexity Predictions, have students test binary search on an unsorted array and observe the linear-time behavior, then reinforce that Big O assumes valid input conditions and requires verification in practice.

---

Methods used in this brief

• Problem-Based Learning