AP CSP Topic 3.17 Guided Notes - Algorithmic Efficiency

Big Idea 3: Algorithms and Programming · Topic 3.17 · Guided Notes (Student)

Algorithmic Efficiency — Guided Notes

Fill these in during class or catch up here if you were absent. Print this page or work on paper — then check yourself with the CFUs on the Topic 3.17 page.

Print these notesAll CSP topics

Day 1: How Much Work Is That?

Today’s objectives

  • Distinguish a PROBLEM from an INSTANCE of that problem, and tell a decision problem (yes/no) apart from an optimization problem (the best answer) (LO AAP-4.A)
  • Estimate an algorithm's efficiency informally by counting how many times a statement runs, and express that cost as it depends on the size of the input (LO AAP-4.A)

Bell ringer

With your group, count the number of unique HANDSHAKES if everyone shakes hands with everyone else exactly once. Work it out for a group of 4 people, then 8 people, then predict for 40 — every pair counts once, and no one shakes their own hand.

Write 2–4 sentences: when the group doubled from 4 to 8, did the number of handshakes double, or grow faster? Estimate the handshakes for 40 people WITHOUT drawing them all. What does this suggest about how the amount of work depends on the size of the group?

01. Problems, Instances, and Kinds of Problems

Key Vocabulary (LO AAP-4.A)

Term Definition (write it)
Problem
Instance
Decision problem
Optimization problem
Efficiency

A Problem, and One Instance of It

  • A problem describes the general task, while an instance of it adds .
  • A single problem can have .
  • We study the efficiency of the algorithm across input sizes rather than one instance because .

Decision vs Optimization Problems

Decision problem

Optimization problem

  • A decision problem is one whose answer is .
  • An optimization problem asks not whether a solution exists but .

AP TIP: 'Is there…' / 'Does it…' signals a DECISION problem; 'what is the best / shortest / largest…' signals an OPTIMIZATION problem.

Stop and think

  1. In your own words, explain the difference between a problem and an instance, then give one problem of your own and two different instances of it.
  2. Label each as a decision or an optimization problem, and rewrite the OTHER version of each: (a) 'Is there a flight from Chicago to Tokyo?' (b) 'What is the cheapest flight from Chicago to Tokyo?'
  3. A classmate says 'sorting the list (5, 2, 9) is a problem.' Correct the wording precisely — what is the problem, and what is (5, 2, 9)?

Answer in complete sentences. Then check yourself with the matching CFUs on the Topic 3.17 page.

02. Measuring Efficiency by Counting

Efficiency Is About Growth, Not the Clock

  • Efficiency is best thought of not as clock time but as .
  • At this level we measure an algorithm's efficiency informally by .
  • The CED explicitly keeps out of this course.

One Loop: Work Grows With n

The comparison inside the loop runs once per element, so a list of n names costs about n checks.

AP Pseudocode (what the exam tests)

FOR EACH name IN roster
{
  IF(name = target)
  {
    DISPLAY("found")
  }
}

Python (the runnable version)

for name in roster:
    if name == target:
        print("found")

Run and edit this yourself in the coding exercises for this topic.

A Loop Inside a Loop: Work Grows With n × n

For every person, the inner loop runs through everyone again — so the inner check runs about n × n times.

AP Pseudocode (what the exam tests)

FOR EACH a IN people
{
  FOR EACH b IN people
  {
    IF(a = b)
    {
      DISPLAY("match")
    }
  }
}

Python (the runnable version)

for a in people:
    for b in people:
        if a == b:
            print("match")

Run and edit this yourself in the coding exercises for this topic.

Two Correct Algorithms, Very Different Costs

Both algorithms are CORRECT. Count how many times the inner check runs as n grows. Fill in the blank cells before we compare.

Complete the empty cells.

Input size n One loop — checks ≈ n Loop inside a loop — checks ≈ n × n
5 5 25
10 10
20 400
50 50

Watch out — “A Faster Computer Makes the Algorithm More Efficient”

Myth: If an algorithm is slow, running it on a faster computer makes it a more efficient algorithm.

Explain why this is wrong:

Stop and think

  1. For the single loop over a list of n items, how many times does the check run when n = 100? For the nested loop over the same list? Show the count for each.
  2. Explain in two sentences why we say the nested-loop algorithm's work grows 'with the square of n,' using the words input size and executes.
  3. Two correct algorithms solve the same problem; one runs about n times and the other about n × n times. Which is more efficient for large n, and how did you decide WITHOUT running either one?
  4. A classmate says 'my algorithm took 3 seconds, so it is efficient.' State the one piece of information their claim is missing.

Show every count. Then check yourself with the matching CFUs on the Topic 3.17 page.

Today in one box

  • A PROBLEM is a general task; an INSTANCE adds specific input — sorting is a problem, sorting (2,3,1,7) is an instance
  • A DECISION problem has a yes/no answer; an OPTIMIZATION problem asks for the best solution among many
  • Efficiency is an estimate of resources as a FUNCTION of input size — measured informally by counting statement executions; formal Big-O is excluded
  • Different correct algorithms for the same problem can have very different efficiencies — a nested loop (n×n) grows far faster than a single loop (n)

Before next class: Before tomorrow, predict it: to check every possible order of 20 delivery stops you would examine about 20 factorial routes — that is over 2 billion billion. If a computer checked a billion routes per second, roughly how many YEARS would that take? Write your estimate and your reasoning.

Day 2: Reasonable, Unreasonable, and Good Enough

Today’s objectives

  • Classify an algorithm as running in REASONABLE time (polynomial or slower — constant, linear, square, cube) or UNREASONABLE time (exponential, factorial) from how its work grows (LO AAP-4.A)
  • Identify situations where a HEURISTIC solution may be more appropriate than an exact one, because a guaranteed-optimal method would be impractical (LO AAP-4.A)

Bell ringer

Yesterday's teaser, now decide it. Checking every possible order of 20 delivery stops means examining about 20 factorial routes — roughly 2.4 × 10¹⁸ (over two billion billion). At a billion routes per second, estimate how long the check would take.

Write down your estimate in years, and your reasoning. Then answer: would buying a computer 1,000 times faster make this approach practical? Why or why not — and if checking every route is hopeless, what would you do instead to get a route you could actually use?

01. Reasonable vs Unreasonable Time

Key Vocabulary (LO AAP-4.A)

Term Definition (write it)
Reasonable time
Unreasonable time
Polynomial efficiency
Exponential efficiency
Factorial efficiency

The Reasonable / Unreasonable Line

  • Algorithms that run in a reasonable amount of time are those with .
  • The CED's two named examples of unreasonable running time are .
  • Faster hardware cannot rescue an unreasonable algorithm because .

When the Numbers Explode

Each column shows how many operations an algorithm does for input size n. The first two stay manageable; the last two run away. Fill in the blanks, then label each column reasonable or unreasonable.

Complete the empty cells.

Input size n Linear (n) — reasonable Square (n²) — reasonable Exponential (2ⁿ) — unreasonable Factorial (n!) — unreasonable
5 5 25 120
10 100 1,024 3,628,800
20 20 1,048,576 2.4 × 10¹⁸
40 40 1,600 ~1.1 × 10¹²

Watch out — “Unreasonable Just Means It Takes a Few Minutes”

Myth: An algorithm that runs in 'unreasonable time' is just a bit slow — a few minutes instead of a few seconds — and waiting or upgrading fixes it.

Explain why this is wrong:

Stop and think

  1. Classify each as reasonable or unreasonable time, and name the growth: (a) work grows like n², (b) work grows like 2ⁿ, (c) work grows like n, (d) work grows like n!.
  2. In two sentences, explain why 'buy a faster computer' does NOT move a factorial-time algorithm from unreasonable to reasonable. Use the word growth.
  3. An algorithm's work grows like n³ (cube). A classmate calls it unreasonable 'because cubing is a big jump.' Correct them: which side of the line is n³ on, and why?
  4. In one sentence, state the CED's rule for which efficiencies count as reasonable and which count as unreasonable.

Answer in complete sentences. Then check yourself with the matching CFUs on the Topic 3.17 page.

02. When to Reach for a Heuristic

Key Vocabulary (LO AAP-4.A)

Term Definition (write it)
Approximate solution
Heuristic
Optimal solution

When No Efficient Algorithm Exists

  • When a problem has no efficient algorithm, instead of the exact best answer we .
  • A heuristic produces a solution that is .
  • The CED excludes from the exam, so you learn the concept and the when, not a recipe.

Exact Solution vs Heuristic

Exact (optimal) method

Heuristic approach

  • An exact optimal method guarantees the best answer but .
  • A heuristic is the appropriate choice when .

AP TIP: A heuristic is the right choice when the problem has no efficient exact algorithm AND a good-enough answer is acceptable — trade the guarantee for a result you can actually get.

Watch out — “A Heuristic Is Just a Lazy Guess That's Always Wrong”

Myth: Using a heuristic means giving up and guessing randomly, so its answer is basically worthless.

Explain why this is wrong:

Stop and think

  1. In your own words, define a heuristic in one sentence, and name the two conditions that together make a heuristic the appropriate choice.
  2. For each, say whether a heuristic is appropriate and why: (a) sorting a list of 50 names, (b) planning the shortest route that visits 100 cities, (c) adding two numbers.
  3. A classmate says 'a heuristic always gives the wrong answer.' Correct the wording precisely — what does 'not guaranteed to be optimal' actually mean?
  4. Explain why 'buy a faster computer' is often NOT a real fix for a problem with no efficient algorithm, and what we do instead (name it).

Answer in complete sentences. Then check yourself with the matching CFUs on the Topic 3.17 page.

Common AP Traps

Three ways Topic 3.17 loses points on the exam — one minute now, real points in May.

Reasonable/unreasonable is about GROWTH, not the clock — in your own words:

A faster computer never changes the efficiency class — in your own words:

'Heuristic' ≠ 'wrong guess' — in your own words:

Algorithmic Efficiency, in One Slide

  • A problem is a general task; an instance adds specific input. Decision problems answer yes/no; optimization problems seek the best among many.
  • Efficiency is a function of input size, measured informally by counting statement executions; different correct algorithms can differ greatly, and formal Big-O is excluded.
  • Reasonable time = polynomial or slower (constant, linear, square, cube); unreasonable time = exponential or factorial — a category of growth, not a stopwatch.
  • When no efficient algorithm exists, seek an approximate solution: a heuristic gives a good-enough, not-guaranteed-optimal answer when the exact method is impractical.

Exit check — I can…

  • ☐  distinguish a problem from an instance, and a decision problem from an optimization problem (LO AAP-4.A)
  • ☐  measure efficiency informally by counting statement executions as a function of input size, without formal Big-O (LO AAP-4.A)
  • ☐  classify an algorithm's running time as reasonable (polynomial or slower) or unreasonable (exponential, factorial) (LO AAP-4.A)
  • ☐  identify when a heuristic is the appropriate choice — no efficient exact algorithm exists and a good-enough answer is acceptable (LO AAP-4.A)

Get in Touch

Whether you're a student, parent, or teacher — I'd love to hear from you.

Just want free AP CS resources?

Enter your email below and check the subscribe box — no message needed. Students get daily practice questions and study tips. Teachers get curriculum resources and teaching strategies.

Typically responds within 24 hours
✓

Message Sent!

Thanks for reaching out. I'll get back to you within 24 hours.

🏫 Welcome, fellow educator!

I offer curriculum resources, practice materials, and study guides designed for AP CS teachers. Let me know what you're looking for — whether it's classroom materials, a guest speaker, or Teachers Pay Teachers resources.

✉

Email

[email protected]

📚

Courses

AP CSA, CSP, & Cybersecurity

⏱

Response Time

Within 24 hours

Prefer email? Reach me directly at [email protected]