Analyzing Algorithm Efficiency: Step Counting

Active tracing makes abstract efficiency concepts visible for students. When learners physically mark comparisons or count loops in real time, they see how steps grow differently across algorithms and datasets. This hands-on work replaces guesswork with clear patterns they can explain and defend.

• Secondary 4
• Computing
• 4 activities
• 25 min–45 min

Learning Objectives

1. Calculate the exact number of comparison operations for linear search on a list of N elements.
2. Calculate the exact number of comparison operations for binary search on a list of N elements.
3. Compare the step counts of linear search and binary search for specific dataset sizes (e.g., N=10, N=100).
4. Predict how the step count of a simple iterative algorithm will change as the input size doubles.
5. Explain why counting steps provides a practical measure of algorithm efficiency for small to medium datasets.

Problem-Based Learning

⏱ 35 min·Pairs

Pair Trace-Off: Linear vs Binary Search

Provide pairs with sorted number cards and unsorted lists. One student traces linear search steps aloud, counting comparisons; the partner does binary search. They swap roles, tally totals, and graph results for n=10 and n=20. Discuss patterns in a 5-minute share-out.

Prepare & details

Explain how counting steps helps us understand an algorithm's efficiency.

Facilitation Tip: During Pair Trace-Off, have students alternate roles as tracer and recorder every two steps to keep both engaged.

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

Problem-Based Learning

⏱ 45 min·Small Groups

Small Group Scaling Predictions

Groups receive algorithm pseudocode for bubble sort and selection sort. Predict step counts for input sizes 5, 10, 20; trace the smallest to verify. Plot predictions on shared graphs and adjust based on actual traces. Compare group graphs class-wide.

Prepare & details

Compare the number of steps taken by linear search versus binary search for a given dataset size.

Facilitation Tip: For Small Group Scaling Predictions, provide calculators to avoid arithmetic slowing the conceptual work.

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

Problem-Based Learning

⏱ 40 min·Small Groups

Whole Class Physical Search Relay

Divide class into teams with card decks representing datasets. Teams race to find a target using linear or binary search rules, counting steps per relay member. Record team totals, then analyze why binary teams finish faster for larger decks.

Prepare & details

Predict how the number of steps in a simple algorithm changes as the input size increases.

Facilitation Tip: In the Whole Class Physical Search Relay, set a three-minute timer per round to maintain momentum and pressure.

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

Problem-Based Learning

⏱ 25 min·Individual

Individual Algorithm Auditor

Students pick a simple loop-based algorithm from notes. Trace it solo for three input sizes, count steps in a table, and predict for n=100. Pair up briefly to verify counts and refine predictions.

Prepare & details

Explain how counting steps helps us understand an algorithm's efficiency.

Facilitation Tip: Assign the Individual Algorithm Auditor role only after students have practiced together; solo work reveals gaps in shared understanding.

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

Teaching This Topic

Teachers should model step counting aloud with think-alouds, especially when loops or nested conditions appear. Avoid rushing to formulas; let students derive the relationship between input size and steps before introducing Big O notation. Research shows that students grasp efficiency best when they first see the raw counts and only later abstract them into general rules.

What to Expect

Successful learning looks like students tracing searches step-by-step, quantifying operations, and justifying why one algorithm scales better than another. They should use data to compare growth rates, predict behavior on larger inputs, and articulate trade-offs between sorted and unsorted data.

Watch Out for These Misconceptions

Common Misconception

During Pair Trace-Off, watch for students assuming both searches take similar steps on larger lists.

What to Teach Instead

Have pairs recount steps on 16-item and 32-item lists, then graph the results side by side to expose linear versus logarithmic growth.

Common Misconception

During Pair Trace-Off, watch for students applying binary search to unsorted data without noticing it fails.

What to Teach Instead

After they try, hand them a small unsorted deck of cards and ask them to sort it first, then count the steps binary search would take if forced to run; they will see extra operations appear.

Common Misconception

During Individual Algorithm Auditor, watch for students equating fewer lines of code with fewer executed steps.

What to Teach Instead

Give each student a snippet with a single loop that spans two lines but runs N times; have them tally the loop body operations to reveal the hidden repetitions.

Assessment Ideas

Quick Check

After Pair Trace-Off, collect students' step-count tables for a 16-item sorted list and ask them to compare the totals for linear versus binary search in a short written reflection.

Exit Ticket

During Small Group Scaling Predictions, have each group submit their predicted step counts for a 64-item list before the class discusses the actual counts, then collect exit tickets showing their predictions and reasoning.

Discussion Prompt

After the Whole Class Physical Search Relay, pose the question: 'If the list were 10 times larger, would the gap between linear and binary search step counts grow wider or stay the same?' and circulate to listen for references to logarithmic versus linear growth.

Extensions & Scaffolding

• Challenge students to design a hybrid search that switches from linear to binary once the unsorted portion shrinks below a threshold, then predict its step count on a dataset of 10,000 items.
• Scaffolding: Provide pre-printed grids for tracing so students focus on marking comparisons rather than redrawing tables.
• Deeper: Ask students to write pseudocode for an algorithm whose step count grows quadratically, then trace it on small and large datasets to observe the sharp increase.

Key Vocabulary

Step Count	The total number of elementary operations, such as comparisons or assignments, performed by an algorithm for a given input.
Operation	A single, basic action performed by an algorithm, like checking if two values are equal or assigning a value to a variable.
Input Size	The quantity of data that an algorithm processes, often represented by a variable like 'N'.
Linear Search	An algorithm that checks each element of a list sequentially until the target is found or the list ends.
Binary Search	An efficient algorithm that finds the position of a target value within a sorted list by repeatedly dividing the search interval in half.