AP® Computer Science Principles review sheet from Aim for Five (aimforfive.com/csp/units/3/3-17)
Unit 3 · Topic 3.17
3.17 Algorithmic Efficiency
Some algorithms stay fast as the input grows; others become hopelessly slow. This topic covers how to measure efficiency informally, the difference between reasonable and unreasonable running time, and why heuristics are used when the perfect answer would take too long.
Key terms
- efficiency
- reasonable time
- unreasonable time
- heuristic
- optimization problem
Problems, instances and kinds of problems
A problem is a general task that may (or may not) be solvable by an algorithm, like "sort a list." An instance is that problem with a specific input, like sorting [9, 4, 6].
A decision problem has a yes-or-no answer: "Is there a route from my house to the stadium?" An optimization problem asks for the best answer among many: "What is the shortest route?"
Measuring efficiency
Efficiency is an estimate of how much computing resources, mainly time and memory, an algorithm uses. It's described in terms of the size of the input: how does the work grow as the list gets longer?
You can measure it informally by counting how many times a statement or group of statements runs for an input of size n. Different correct algorithms for the same problem can have very different efficiencies, as linear and binary search do. Efficiency can also be worked out with formal math, but you won't be asked for formal analysis or Big-O notation.
Reasonable versus unreasonable time
An algorithm runs in a reasonable amount of time if its number of steps grows no faster than a polynomial in n: for example constant, n, n² or n³. An algorithm whose steps grow exponentially (like 2ⁿ) or factorially (n!) runs in an unreasonable amount of time.
| n | n² | 2ⁿ | n! |
|---|---|---|---|
| 10 | 100 | 1,024 | 3,628,800 |
| 20 | 400 | 1,048,576 | about 2.4 × 10¹⁸ |
| 40 | 1,600 | about 1.1 × 10¹² | far too many to list |
Why the difference matters
Doubling n from 20 to 40 multiplies n² by 4, but multiplies 2ⁿ by about a million. For large inputs, an unreasonable algorithm could take longer than a lifetime even on the fastest computers.
A classic example is finding the shortest route that visits every city on a list exactly once. Checking every possible order works for 5 cities, but the number of orders grows factorially, so it's unreasonable for 50.
Heuristics
Some problems have no known efficient algorithm. Then people settle for an approximate solution. A heuristic is an approach that finds a solution that isn't guaranteed to be the best, used when finding a guaranteed best solution would take too long.
For the route problem, one heuristic is "always drive to the closest city you haven't visited yet." It's fast and usually gives a decent route, though not always the shortest. You won't be tested on specific heuristics like this one, only on when a heuristic makes sense.
Worked examples
Try each one yourself first, then open the solution.
- Example 1
Counting statement executions
How many times does
count ← count + 1run in each segment, in terms of n? Which grows faster? Segment 1:count ← 0 REPEAT n TIMES { REPEAT n TIMES { count ← count + 1 } } DISPLAY(count)Segment 2:count ← 0 REPEAT n TIMES { count ← count + 1 } REPEAT n TIMES { count ← count + 1 } DISPLAY(count)Show the solutionHide the solution
- Step 1: Segment 1: the inner loop runs n times for each of the n passes of the outer loop, so the statement runs n × n = n² times. For n = 10 it displays 100.
- Step 2: Segment 2: two loops one after the other, each n times, so 2n times. For n = 10 it displays 20.
- Step 3: Double n to 20: segment 1 gives 400 (4 times as many), segment 2 gives 40 (2 times as many).
- Step 4: Both are polynomial, so both run in a reasonable amount of time, but segment 1 grows faster.
Answer: Segment 1 runs it n² times; segment 2 runs it 2n times. Segment 1 grows faster, but both are reasonable.
- Example 2
When is a heuristic appropriate?
A delivery company must plan routes for 300 stops every morning. The only known way to guarantee the shortest route checks every possible order of stops. Should it use that method or a heuristic? Explain.
Show the solutionHide the solution
- Step 1: The number of possible orders grows factorially with the number of stops, so with 300 stops the guaranteed method would take an unreasonable amount of time.
- Step 2: The routes are needed every morning, so a fast, good-enough route is more useful than a perfect one that never finishes.
Answer: A heuristic: finding the guaranteed shortest route would take an unreasonable amount of time, while a heuristic gives a good route quickly.
Common mistakes
- Thinking n² or n³ is unreasonable because it grows fast. Polynomial growth counts as reasonable; exponential and factorial don't.
- Thinking a faster computer fixes an unreasonable algorithm. Exponential growth outruns any speedup for large inputs.
- Believing a heuristic finds the best answer. It finds a good-enough answer, quickly.
On the exam
- Expect questions that describe how an algorithm's steps grow (like doubling with each added item) and ask whether it runs in reasonable time. Doubling per item is exponential, so unreasonable.
- You may be asked to count how many times a statement runs in a loop for a given input size.
Connected topics
Videos
Check yourself
4 questions on 3.17 Algorithmic Efficiency. Pick an answer to see if you got it, and why.
Four algorithms take the following numbers of steps for an input of size n. Which two run in an unreasonable amount of time? Select two answers.
Select two answers. 0 of 2 chosen
In the code segment below, n is a positive integer. When n is 10, how many times does the statement count ← count + 1 run, and how does the algorithm's running time grow?
count ← 0
REPEAT n TIMES
{
REPEAT n TIMES
{
count ← count + 1
}
}
A delivery company needs a route through 60 stops. Checking every possible order of the stops would take far longer than the age of the universe, so the company's program builds a route by always driving to the closest stop not yet visited. Which statement best describes this approach?
Which of the following is a decision problem rather than an optimization problem?
0 of 4 answered