Comparing Algorithm Efficiency

Active learning helps students grasp algorithm efficiency because abstract concepts like time complexity become visible through hands-on trials. When students physically count steps or time code runs, they connect mathematical patterns to real-world performance in ways that lectures alone cannot achieve.

• Year 9
• Technologies
• 4 activities
• 30 min–45 min

Learning Objectives

1. Compare the number of steps required by a linear search algorithm versus a simpler search method for a given input size.
2. Analyze how the number of operations changes for different search algorithms as the size of the data list increases.
3. Predict which search algorithm will perform more efficiently on a very large dataset and justify the prediction.
4. Evaluate the suitability of different algorithmic approaches for solving the same problem based on computational efficiency.

Inquiry Circle

⏱ 35 min·Small Groups

Card Simulation: Linear vs Binary Search

Provide shuffled numbered cards as lists. Groups perform linear search by checking sequentially and binary search by halving sorted piles, recording steps for lists of 10, 20, and 40 items. Discuss patterns in step counts as sizes increase.

Prepare & details

Compare how a linear search finds an item versus a simpler search method.

Facilitation Tip: During Card Simulation: Linear vs Binary Search, have students record every comparison on scrap paper to make the hidden work of algorithms visible.

Setup: Groups at tables with access to source materials

Materials: Source material collection, Inquiry cycle worksheet, Question generation protocol, Findings presentation template

• Analyze
• Evaluate
• Create
• Self-Management
• Self-Awareness

Inquiry Circle

⏱ 45 min·Pairs

Coding Duel: Search Timings

Pairs write simple linear and binary search functions in Python or pseudocode. Test on lists of growing sizes, measure execution steps or approximate times using loops. Graph results to compare scalability visually.

Prepare & details

Predict which algorithm might be 'faster' for a very large list of items.

Facilitation Tip: In Coding Duel: Search Timings, assign roles so one student writes code while the other times and records results, ensuring both students engage with the data.

Setup: Groups at tables with access to source materials

Materials: Source material collection, Inquiry cycle worksheet, Question generation protocol, Findings presentation template

• Analyze
• Evaluate
• Create
• Self-Management
• Self-Awareness

Inquiry Circle

⏱ 30 min·Whole Class

Prediction Walkthrough: Step Counts

Individuals predict steps for sample algorithms on paper inputs of varying sizes. Share predictions in whole class walkthroughs, then verify by tracing actual paths. Adjust predictions based on class evidence.

Prepare & details

Justify why one way of solving a problem might be better than another for a computer.

Facilitation Tip: For Prediction Walkthrough: Step Counts, pause after each prediction to ask students to explain their reasoning before revealing outcomes.

Setup: Groups at tables with access to source materials

Materials: Source material collection, Inquiry cycle worksheet, Question generation protocol, Findings presentation template

• Analyze
• Evaluate
• Create
• Self-Management
• Self-Awareness

Inquiry Circle

⏱ 40 min·Small Groups

Relay Race: Algorithm Actors

Divide class into teams acting as algorithms. One student per team represents data elements; others search linearly or by dividing. Time races for different team sizes and tally operations to reveal efficiency.

Prepare & details

Compare how a linear search finds an item versus a simpler search method.

Facilitation Tip: In Relay Race: Algorithm Actors, use a visible timer projected on the board so the class sees how small delays compound across steps.

Setup: Groups at tables with access to source materials

Materials: Source material collection, Inquiry cycle worksheet, Question generation protocol, Findings presentation template

• Analyze
• Evaluate
• Create
• Self-Management
• Self-Awareness

Teaching This Topic

Teachers should connect efficiency to real decisions, like choosing between searching a bookshelf by scanning each book versus using a card catalog. Avoid overemphasizing code syntax during these lessons; focus instead on the relationship between input size and operation counts. Research shows students grasp Big O best when they first experience inefficiency physically before formalizing it mathematically.

What to Expect

Students will clearly articulate why linear search slows as lists grow while binary search remains efficient. They will use operation counts and timing data to justify choices between algorithms, showing confidence in predicting scalability.

Watch Out for These Misconceptions

Common Misconception

During Card Simulation: Linear vs Binary Search, watch for students who assume binary search works on unsorted lists because they see cards in hand.

What to Teach Instead

In Card Simulation: Linear vs Binary Search, have students shuffle the cards first to demonstrate that binary search requires a sorted list, then ask them to explain why order matters for halving the search space.

Common Misconception

During Coding Duel: Search Timings, watch for students who equate faster code execution with more efficient code.

What to Teach Instead

In Coding Duel: Search Timings, guide students to compare total operation counts alongside timings, prompting them to notice that code structure affects steps differently than raw speed.

Common Misconception

During Relay Race: Algorithm Actors, watch for students who focus only on speed and ignore the number of operations or memory use.

What to Teach Instead

In Relay Race: Algorithm Actors, have teams present both their step counts and timing results, requiring them to justify efficiency based on multiple metrics during the discussion.

Assessment Ideas

Quick Check

After Card Simulation: Linear vs Binary Search, provide students with a new sorted list twice as long and ask them to predict the linear and binary search step counts before performing the search.

Discussion Prompt

During Coding Duel: Search Timings, ask each pair to share one realization about speed versus efficiency they discovered while timing their searches, then discuss as a class.

Exit Ticket

After Prediction Walkthrough: Step Counts, have students write a short reflection comparing their initial predictions to the actual step counts they recorded, explaining which algorithm felt more scalable and why.

Extensions & Scaffolding

• Challenge: Ask students to design a hybrid search that switches from linear to binary when a list exceeds a certain size, then test its efficiency.
• Scaffolding: Provide partially filled comparison charts for students to complete during Card Simulation to reduce cognitive load.
• Deeper exploration: Have students research and present on alternative search algorithms like interpolation search or exponential search, comparing their efficiency in different scenarios.

Key Vocabulary

Algorithm	A step-by-step procedure or set of rules for solving a problem or completing a task.
Input Size	The quantity of data that an algorithm must process, such as the number of items in a list.
Operation	A single action or step performed by an algorithm, such as a comparison or an assignment.
Efficiency	A measure of how well an algorithm uses resources, particularly time (number of operations) and memory, relative to the input size.
Linear Search	A simple search algorithm that checks each element in a list sequentially until the target item is found or the list ends.