When does an algorithm take so long it's practically impossible to run?
In our last lesson we compared two search algorithms. What makes binary search more efficient than linear search?
We already found algorithms for checking whether a specific ticket number was in a list.
Today we change the question: we want to find combinations of tickets rather than a single one.
As we work, pay attention to how many "checks" each new algorithm requires.
The big question: do those check counts grow at a reasonable or unreasonable rate?
The Problem
The winner is the one ticket whose number exactly matches the winning number.
Scan the QR code on your phone to receive your ticket number. Once everyone has a number, see whether anyone has the one winning ticket.
The Problem
The winners are any two tickets whose numbers add up to the winning sum.
Using the same ticket numbers from the regular raffle, work together to figure out whether any pair of tickets adds up to the winning sum.
The Problem
The winners are any group of tickets (from one up to all of them) whose numbers add up to the winning sum.
Using the same ticket numbers from the pair raffle, now try to find a group of any size (one ticket, two, three, or all of them) whose numbers sum to the winning number. Work together to search for a winning group.
With your partner, fill in both tables on your activity guide. For each number of tickets, count how many checks your algorithm would need to make in the worst case.
For the pair raffle, count each distinct two-ticket pair. For the group raffle, count the groups of any size (from one to all).
Hint for pairs: if you have tickets A, B, C, the pairs are AB, AC, and BC. Try drawing lines between the tickets to count them.
| Pair Raffle | |
|---|---|
| Tickets | Checks |
| 2 | ? |
| 3 | ? |
| 4 | ? |
| 5 | ? |
| 8 | ? |
| Group Raffle | |
|---|---|
| Tickets | Checks |
| 2 | ? |
| 3 | ? |
| 4 | ? |
| 5 | ? |
| 8 | ? |
| Tickets (n) | Pair Checks |
|---|---|
| 2 | 1 |
| 3 | 3 |
| 4 | 6 |
| 5 | 10 |
| 8 | 28 |
The number of checks grows faster than the number of tickets. Adding one more ticket always adds more new pairs than the last ticket did.
The exact relationship is (n² − n) / 2. Because of the n² term, this curve bends upward. Algorithms with an n² term are called polynomial.
Pair Raffle — Checks vs. Tickets
| Tickets (n) | Group Checks |
|---|---|
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 8 | 255 |
Each additional ticket more than doubles the number of checks. The values (3, 7, 15, 31, 63, 127, 255) are each one less than a power of 2.
The exact relationship is 2n − 1. Because of the 2n term, this curve bends upward extremely fast. Algorithms with a 2n term are called exponential.
Group Raffle — Checks vs. Tickets
When every flap is showing 1, the total value is the number of checks you need. Think of each ticket as a binary place value.
| Tickets (n) | Group Checks | As binary |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 3 | 11 |
| 3 | 7 | 111 |
| 4 | 15 | 1111 |
| 5 | 31 | 11111 |
| 8 | 255 | 11111111 |
The number of group-raffle checks is always the largest number you can make with that many bits when every bit is 1. That is exactly 2n − 1.
Every flap is a 1: flip them all to find the total checks.
Both polynomial (pair raffle) and exponential (group raffle) curves bend upward as n grows. Why do you think only exponential is considered to run in an unreasonable amount of time?
Checks grow as roughly n². Doubling the tickets quadruples the work. That is a lot, but a faster computer or some optimization might still make it feasible.
Checks grow as 2n. Adding just one more ticket doubles all the work. Even the fastest computers cannot keep up once n gets large.
Set n with the slider and press Start. The app simulates each algorithm working through its checks at the same pace. Discuss with a partner: which algorithms still seem reasonable as n grows?
Try n = 10, then n = 20, then n = 25. What changes?
Algorithms whose check count grows as a polynomial power of n (constant, linear, n², n³, etc.) run in reasonable time. They can be slow for large n, but a faster computer or better implementation can still make progress.
Sorted Raffle (logarithmic): reasonable.
Normal Raffle (linear): reasonable.
Pair Raffle (polynomial n²): reasonable.
Algorithms whose check count grows as an exponential (2n, 3n, etc.) or factorial run in unreasonable time. Even with the fastest computers imaginable, adding one more item to the input can make the algorithm take exponentially longer to complete.
Group Raffle (exponential 2n): unreasonable.
Note: the line between reasonable and unreasonable is drawn at polynomial versus exponential — not at any specific number of steps.
| Tickets (n) | Sorted Raffle log2(n) — reasonable |
Normal Raffle n — reasonable |
Pair Raffle n2 — reasonable |
Group Raffle 2n — unreasonable |
|---|---|---|---|---|
| 10 | 4 | 10 | 100 | 1,024 |
| 20 | 5 | 20 | 400 | 1,048,576 |
| 100 | 7 | 100 | 10,000 | 1.27 × 1030 |
| 1,000 | 10 | 1,000 | 1,000,000 | 1.07 × 10301 |
| 10,000 | 14 | 10,000 | 100,000,000 | 2.00 × 103010 |
By n = 1,000 the group raffle requires roughly 10301 checks. The observable universe contains an estimated 1080 atoms: the algorithm needs far more checks than that, and no amount of faster hardware changes this.
An algorithm processes a list of n items. As n doubles, the number of steps the algorithm takes roughly quadruples. What best describes this algorithm?