BIG IDEA 3: ALGORITHMS AND PROGRAMMING · TOPIC 3.17
3.17 Algorithmic Efficiency
How does the work an algorithm does grow as the input grows? The CED draws one line — polynomial vs. exponential — and everything here follows from it.
What you need to know
- Efficiency is measured by how the number of steps (or memory) an algorithm needs grows as the input size grows — not by a stopwatch on one computer.
- An algorithm runs in reasonable time if its steps grow polynomially with input size: constant, linear (n), quadratic (n²), cubic, etc.
- An algorithm runs in unreasonable time if its steps grow exponentially (2n) or factorially (n!). Doubling the input can square or worse the time — these become impossible for even modest inputs.
- Comparing algorithms: count the operations as a function of n. Linear search is about n steps; binary search about log₂ n; comparing every pair of items is about n².
- Some problems have no known reasonable-time algorithm. For these, a heuristic — an approach that finds a good-enough, not necessarily optimal, solution quickly — is used instead.
- Heuristic example: the traveling salesperson problem (shortest route visiting every city). Checking all routes is factorial time; "always go to the nearest unvisited city" is a fast heuristic that gives a decent route.
- Efficiency often involves a trade-off with simplicity or memory. The most efficient algorithm isn't always the best choice for a small, one-time task.
Worked example
Two algorithms check whether a list of n names contains any duplicate.
- Algorithm A: compare every name to every other name. For n = 10 that's about 45 comparisons; for n = 1,000, about 500,000. Steps grow roughly as n² — polynomial, so reasonable.
- Algorithm B: try every possible ordering of the list looking for a pattern. For n = 10 that's 3.6 million orderings; for n = 20, over 2 quintillion. Factorial — unreasonable.
A is slower than a smarter approach but fine; B is unusable past tiny inputs no matter how fast the computer is.
Exam tip: If a question gives a table of input size vs. steps, check the growth: steps doubling when n increases by 1 = exponential = unreasonable. Steps multiplying by 4 when n doubles = n² = reasonable. When the stem says "no efficient algorithm exists" or "the solution doesn't have to be perfect," the answer involves a heuristic.
Going deeper
The nuance, edge cases, and connections that turn a 3 into a 5.
- The CED defines efficiency by how an algorithm's resource use (steps or memory) grows with input size, and draws one line: polynomial growth (constant, linear, quadratic, cubic…) is reasonable; exponential (2n) or factorial (n!) growth is unreasonable.
- Why the line is there: doubling the input for a quadratic algorithm quadruples the work — manageable. Doubling the input for an exponential algorithm squares the work. At n = 50, 2n is a quadrillion. No hardware improvement fixes that.
- Recognizing growth from a table: steps double when n increases by 1 → exponential. Steps multiply by 4 when n doubles → quadratic. Steps double when n doubles → linear. Steps increase by 1 when n doubles → logarithmic.
- Reading growth from code: one loop over n items → linear. Nested loops each over n → quadratic. A loop that halves the range each time → logarithmic. Trying every subset or every ordering → exponential or factorial.
- Heuristics are for problems where the exact solution is unreasonable. A heuristic gives a good-enough answer fast, without guaranteeing the best. The traveling salesperson problem (shortest route through all cities) is the canonical example: exact = factorial time; nearest-neighbor heuristic = fast and usually decent.
- A problem can have both reasonable and unreasonable algorithms. Sorting by trying every ordering is factorial; sorting with merge sort is n log n. The problem isn't hard; the first algorithm is just bad.
- The CED explicitly says efficiency is not measured by running time on a specific computer — faster hardware changes the constant, not the growth. An unreasonable algorithm on a supercomputer is still unreasonable.
Mistakes that cost points
- Calling quadratic "unreasonable." It's polynomial, so it's reasonable per the CED. Slow for large n, but reasonable.
- Thinking a faster computer fixes exponential growth. It shifts the wall by a few units of n. It doesn't remove it.
- Expecting a heuristic to find the optimal answer. Heuristics trade optimality for speed. If an option says a heuristic "always finds the best solution," it's wrong.
- Reading a steps table without computing ratios. Look at how steps change as n changes. That ratio is the growth type.
Practice questions
Written in the style of the real exam. Try each one before revealing the answer.
Q1 The table shows the number of steps an algorithm takes for different input sizes.
Which of the following best describes the algorithm?
| Input size | Steps |
|---|---|
| 10 | 1,024 |
| 11 | 2,048 |
| 12 | 4,096 |
Show answer
Answer: B. Steps double each time n increases by 1 — that's 2ⁿ, exponential, unreasonable.
Q2 A delivery company must plan a route through 50 cities. Checking every possible route would take longer than the age of the universe. Which approach is most appropriate?
Show answer
Answer: A. When the exact algorithm is unreasonable, a heuristic gives a usable answer in reasonable time. A faster computer doesn't overcome factorial growth.
Key vocabulary
- Efficiency
- how an algorithm's required steps or memory grow with input size
- Reasonable time
- polynomial growth in steps (n, n², n³ …) as input grows
- Unreasonable time
- exponential or factorial growth in steps as input grows
- Heuristic
- a technique that finds a good-enough solution quickly when an optimal one is impractical