3.17 and 3.18 Algorithmic efficiency and undecidable problemsFast enough, and possible at all

A problem is a general description of a task that may or may not be solvable with an algorithm. An instance of a problem is that problem with a specific input. A decision problem has a yes-or-no answer ("is there a route shorter than 50 miles?"). An optimization problem asks for the best solution among many ("what is the shortest route?").
| Kind of problem | Question it asks | Example |
|---|---|---|
| Decision problem | Yes or no? | Is there a route under 50 miles? |
| Optimization problem | What is the best? | What is the shortest route? |
| Decidable | An algorithm answers every instance | Is this number even? |
| Undecidable | No algorithm answers every instance | Will this program ever stop? |
Efficiency is an estimate of how many computational resources, usually time, an algorithm uses, measured against the size of its input. You can estimate it informally by counting how many times a statement runs. A loop over n items runs its body n times. A loop inside a loop, each over n, runs the inner body n × n times.
1count ← 02REPEAT n TIMES3{4 REPEAT n TIMES5 {6 count ← count + 117 }8}
- line 6 Runs n times for each of n passes: n × n
| n | times count ← count + 1 runs |
|---|---|
| 5 | 25 |
| 10 | 100 |
| 100 | 10,000 |
?Wait, what does "polynomial" mean here?
Algorithms with polynomial efficiency or slower growth (constant, linear, square, cube) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiency are said to run in an unreasonable amount of time: fine for tiny inputs, hopeless for moderately large ones. Different correct algorithms for the same problem can have very different efficiencies, as linear and binary search showed.
| n | n² steps | 2ⁿ steps | 2ⁿ at a billion steps a second |
|---|---|---|---|
| 10 | 100 | 1,024 | about a microsecond |
| 30 | 900 | about 1.07 billion | about a second |
| 40 | 1,600 | about 1.1 trillion | about 18 minutes |
| 70 | 4,900 | about 1.2 sextillion | about 37,000 years |
Heuristics
Some problems can't be solved in a reasonable time because no efficient algorithm for them is known. A delivery driver with 10 stops has 181,440 possible round trips; with 20 stops, about 60 quadrillion. Checking every route is unreasonable. In these cases, we accept an approximate solution. A heuristic is an approach that produces a solution that isn't guaranteed to be the best, but is used when finding the guaranteed best is impractical. "Always drive to the nearest stop you haven't visited" is a heuristic: fast, usually decent, sometimes not optimal.
?Wait, is a heuristic a wrong answer?
Undecidable problems
A decidable problem is a decision problem for which an algorithm can be written that gives the correct output for every input. "Is this number even?" is decidable: n MOD 2 = 0 answers it every time. An undecidable problem is one for which no algorithm can ever be written that always gives a correct yes-or-no answer. Some instances of an undecidable problem may be solvable, but no single algorithm solves all instances. The famous example: given any program and its input, decide whether the program will eventually stop or run forever. Computer scientists have proved no algorithm can answer that for every program.
Keep the two ideas apart. A slow problem, like the delivery routes, is solvable; it just takes too long, so we use heuristics. An undecidable problem can't be solved for all inputs by any algorithm, no matter how fast the computer.
I thought about it. Show me
- (a) Once per pass: 8 times. Linear: doubling n doubles the work.
- (b) 8 passes of the outer loop, each running the inner statement 8 times: 64 times. That's n².
Why?
Multiply the passes of nested loops. - (c) 64, 32, 16, 8, 4, 2, 1: the body runs 6 times before n ≤ 1 is true. Halving each pass grows very slowly, like binary search.
- All three are polynomial or slower growth, so all are reasonable.
Why?
Only growth like 2ⁿ or factorial counts as unreasonable.
Answer: (a) 8 (b) 64 (c) 6. All three run in reasonable time.
Stuck? Get a hint
- For (a), how many passes?
- For (b), multiply outer passes by inner passes.
- For (c), halve 64 until you reach 1 and count the halvings.
- ADeciding whether a whole number is prime
- BFinding the shortest route through 50 cities
- CDeciding, for every possible program and input, whether the program will eventually stop
- DSorting a list of one billion names
Show the answer
C. No algorithm can correctly decide for every program whether it halts: that is the classic undecidable problem. The route problem is solvable but unreasonably slow (heuristics help), and the others are solvable in reasonable time.
- AIt runs in polynomial time, so it is reasonable for large inputs.
- BIt runs in exponential time, so a heuristic may be needed for large inputs.
- CThe problem it solves must be undecidable.
- DDoubling the speed of the computer fixes the problem for any input size.
Show the answer
B. Doubling per added item is 2ⁿ growth: exponential and unreasonable for large n. That calls for a heuristic, not a verdict of undecidable. A twice-as-fast computer only handles one more item in the same time.
- Efficiency: resources (usually time) as a function of input size. Estimate by counting statement executions.
- Polynomial (n, n², n³): reasonable. Exponential (2ⁿ) or factorial: unreasonable.
- A heuristic gives a good-enough, not guaranteed optimal, answer when exact methods are impractical.
- Undecidable: no algorithm gives a correct yes-or-no answer for every input. Slow is not undecidable.