3.17 Algorithmic Efficiency — Counting Steps Draft

On the website: Keep the runner set to Python, edit an example, and click Run. Python runs in your browser; the first run needs an internet connection to download Python.

Lesson draft. Try the examples with a classmate and use their feedback to improve the lesson.

Imagine looking for a number in a list. A list with 5 numbers is easy to check. What changes when it has 500 numbers? In this lesson, we count the steps a computer takes.

What Is Algorithmic Efficiency?

An algorithm is a set of steps for solving a problem. Algorithmic efficiency describes the time and memory those steps need as the input gets bigger.

We use n to mean input size, such as the number of items in a list. Today, we will compare ways to solve the same problem and see how their work grows.

1. LXD Cycle — Comparing Solutions

Empathize: Beginners may assume that two programs giving the same answer do the same amount of work. Ask a partner how they would find a number in a long list.

Define: Learners need to compare correct solutions by the work they need as input grows. Goal: Explain efficiency, compare search strategies, and recognize growth patterns.

Ideate: How might we make efficiency easy to see? Find the same number in two ways, compare checks, and change input sizes in simple Python calculators. For each runner: predict → run → change → explain.

Prototype: This draft uses a short search walkthrough and three step-count calculators. The focus is choosing and explaining an approach.

Test: Ask a peer which search they would choose for 1,000 sorted numbers and why. Then ask whether the same choice works on an unsorted list. Record their answer and any confusing explanation.

Refine: Improve one explanation based on their feedback and have them retry. Peer results are pending.

2. Lesson Plan

Prerequisites: Python variables, numbers, and print. No loop-writing is required.

Success criteria: I can explain efficiency using input size and work, compare two searches fairly, and explain why some growth patterns become impractical.

Read the College Board excerpt below, then explain it in your own words.

College Board Connection

Read Topic 3.17: Algorithmic Efficiency, printed pages 94–95 in the AP CSP Course and Exam Description.

“Efficiency is an estimation of the amount of computational resources used by an algorithm.”

— College Board (2023), p. 94, AAP-4.A.3. Official reading.

In our own words: how much work does a solution need as its input grows? Counting repeated steps applies AAP-4.A.5, and comparing correct solutions applies AAP-4.A.6.

What Are We Measuring?

A correct algorithm gives the right answer. An efficient algorithm uses resources carefully. Check correctness first, then compare efficiency.

• Input size: how much information we give the algorithm, written as n.
• Time efficiency: how the amount of work grows as n grows. We will count inspected items rather than seconds.
• Space efficiency: how much extra memory the algorithm needs. Saving a second copy of a list uses more memory than keeping only a few counters.

A shorter program is not automatically more efficient. A faster computer can reduce waiting, but it does not change the algorithm’s growth pattern.

Example 1: Same Answer, Different Work

Find 15 in this sorted list: [3, 6, 9, 12, 15, 18, 21].

Linear search: Start at the beginning. Inspect 3, 6, 9, 12, then 15. 5 checks.

Binary search: Inspect the middle item, 12. Since 15 is larger, keep the right half. Inspect its middle item, 18. Since 15 is smaller, inspect 15. 3 checks. Each unsuccessful check removes about half the remaining possibilities.

Both find the same number. Here, binary search inspects fewer items. It requires a sorted list with direct access to the middle item. Sorting an unsorted list also costs work, so include that cost when choosing a method.

The runner below compares the counts from this walkthrough; it does not perform the searches.

# CODE_RUNNER: Compare two correct searches for the same number
linear_checks = 5
binary_checks = 3

print("Linear search checks:", linear_checks)
print("Binary search checks:", binary_checks)
print("Checks saved:", linear_checks - binary_checks)

Popcorn Hack 1 — Does One Method Always Win?

Find 3 in the same list by hand. Linear search inspects 3 immediately. Binary search inspects 12, then 6, then 3.

1. Predict the checks for each method, then update the runner.
2. Which method uses fewer checks for this target?
3. Why should we examine more than one target before choosing an algorithm?

Check: Linear uses 1 check and binary uses 3. One easy input does not describe performance on every input. A best case requires the least work; a worst case requires the most for a given input size.

Example 2: What Happens with More Data?

For a list of 1,000 items, linear search may inspect all 1,000. Standard binary search needs at most 10 item inspections on a sorted list.

Linear search has linear growth: doubling the list doubles its worst-case checks. Binary search has logarithmic growth: doubling a nonempty list adds about one worst-case check.

Use the provided calculator below. Change only n to compare list sizes. The math expression calculates binary search’s worst-case item inspections; you do not need to memorize it. These are count models, not timed searches. Use a positive whole number for n.

# CODE_RUNNER: Change the input size and compare worst-case search checks
import math

n = 1000
linear_checks = n
binary_checks = math.floor(math.log2(n)) + 1

print("List size:", n)
print("Linear search: up to", linear_checks, "checks")
print("Binary search on sorted data: up to", binary_checks, "checks")

Popcorn Hack 2 — Compare Growth

1. Run with n = 1000, then n = 2000.
2. Which method’s worst-case work doubles?
3. Which method would you choose for many searches on a large list that is already sorted? Explain using the counts.

Check: Linear: 1,000 → 2,000. Binary: 10 → 11. Binary search scales better for this task when its sorted-data requirement is met.

Example 3: Recognize Growth Patterns

We can compare growth without writing the algorithms themselves. Suppose three approaches to the same task have work estimates of n, n × n, and 2ⁿ. Assume all three produce a correct answer and each counted step has comparable cost.

The calculator models their work. It does not execute that many steps. In Python, ** means “raised to a power.” Try small values such as 5, 10, and 20.

# CODE_RUNNER: Compare how estimated work grows
n = 10

print("Input size:", n)
print("Linear work:", n)
print("Quadratic work:", n ** 2)
print("Exponential work:", 2 ** n)

Popcorn Hack 3 — Small Input, Big Difference

1. Predict the results for n = 10, then run.
2. Change n to 20. Which estimate grows fastest?
3. Which approach would you investigate first for a large input, assuming all are correct and solve the same task?

Check: At 10: 10, 100, 1,024. At 20: 20, 400, 1,048,576. Linear work doubles, quadratic work quadruples, and exponential work grows far more. The linear approach is the promising starting point under these assumptions.

Can an Algorithm Take Too Long?

In AP CSP, linear and quadratic growth count as reasonable time. Exponential growth, such as 2ⁿ, and factorial growth count as unreasonable time as inputs grow (College Board, 2023, AAP-4.A.7).

Trying every possible selection from a list of 10 items means 1,024 possibilities. With 20 items, that becomes 1,048,576! Small inputs may still finish quickly; the concern is how fast the work grows.

A heuristic can produce a useful solution without guaranteeing the best one when finding the best answer is impractical (AAP-4.A.8–9). For example, someone with a list of errands might visit the nearest remaining stop first. This is easy to choose, but it may not give the shortest route overall.

Popcorn Hack 4 — Explain the Tradeoff

Why might someone choose the nearest errand next instead of checking every possible order of stops?

Check: It can give a useful answer sooner, but may miss the shortest route.

3. Efficiency Reference Guide

Growth describes a pattern, not an exact number of seconds. “Reasonable time” is a growth classification, not a promise that every large input finishes quickly. Formal Big O analysis is outside AP CSP exam scope.

Before choosing: Does the algorithm give the right answer? Does its input requirement hold? How does work grow? Does it need extra memory or preparation such as sorting?

4. Knowledge Check

1. Two algorithms give the same correct answer. What helps compare their efficiency? A: Their names; B: Work and memory as input grows; C: Only the number of code lines.
2. Binary search can discard half the remaining list because: A: The list is sorted; B: Every number is positive; C: The computer is fast.
3. Input grows from 1,000 to 2,000. Worst-case binary-search checks grow from 10 to 11. This is: A: Linear growth; B: Quadratic growth; C: Logarithmic growth.
4. An exponential algorithm finishes quickly on 5 items. Does that prove it is practical for 500 items? A: Yes; B: No, its work grows rapidly; C: Yes, if its code is short.

5. Homework Hack — Choose an Algorithm

You must find numbers in an already sorted list. Use the calculator for 100, 1,000, and 10,000 items, saving each result. No search implementation is required.

Write a short recommendation:

1. Which search would you choose for many searches of this list? Support your answer with the counts.
2. What changes if the list is unsorted and you only need one search?
3. Can linear search beat binary search on a particular target? Give an example.
4. What extra resource is needed if you keep a separate sorted copy of the original list?

# CODE_RUNNER: Gather evidence for your algorithm recommendation
import math

n = 100
print("List size:", n)
print("Linear search worst-case checks:", n)
print("Binary search worst-case checks:", math.floor(math.log2(n)) + 1)

# Run again with n = 1000 and n = 10000.
# Explain your choice in a Markdown cell using the results.

Self-check: For 100, 1,000, and 10,000 items, linear-search worst-case counts are 100, 1,000, and 10,000; binary-search counts are 7, 10, and 14. Sorting has a preparation cost, and keeping a separate sorted copy uses extra memory.

Save your work in a Python notebook and keep the calculator output visible. Include your predictions, MCQ score, and answers to the four recommendation questions. Publish using your class portfolio workflow and submit the page link.

Suggested Practice Rubric (1 Point)

Academic Reference

College Board. (2023). AP Computer Science Principles course and exam description (effective fall 2023), Topic 3.17: Algorithmic Efficiency (pp. 94–95), AAP-4.A.3–9. Official PDF.

Structure adapted from: Open Coding Society. (n.d.). 1.02 Variables and Data Types. Example lesson. This draft follows its LXD, lesson, code example, hack, and feedback structure using simple Python list examples.