AP Computer Science Principles · Unit 3 lecture · Part 13 of 14 · 10 min

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

Mr. Thompkins
Two last questions about any problem. First: can a computer solve it in a reasonable amount of time? Second, a stranger one: can a computer solve it at all? The answers are sometimes no and no.

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 problemQuestion it asksExample
Decision problemYes or no?Is there a route under 50 miles?
Optimization problemWhat is the best?What is the shortest route?
DecidableAn algorithm answers every instanceIs this number even?
UndecidableNo algorithm answers every instanceWill this program ever stop?
Kinds of problems the course names.

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}
  1. line 6 Runs n times for each of n passes: n × n
A nested loop: the inner statement runs n² times.
ntimes count ← count + 1 runs
525
10100
10010,000
Doubling n multiplies the work by 4.
?Wait, what does "polynomial" mean here?
An algorithm runs in polynomial time if its steps grow like n, n², n³ or another power of n. Exponential means the steps grow like 2ⁿ: each extra item doubles the work. You don't need formal notation like Big-O; just recognize the patterns.

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.

0246810020040060080010001200input size nstepsnn²2ⁿ
Steps as the input grows. At n = 10, 2ⁿ is already 1,024, ten times n².
nn² steps2ⁿ steps2ⁿ at a billion steps a second
101001,024about a microsecond
30900about 1.07 billionabout a second
401,600about 1.1 trillionabout 18 minutes
704,900about 1.2 sextillionabout 37,000 years
At a billion steps a second, n² stays tiny. 2ⁿ goes from a microsecond to tens of thousands of 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?
No. It's a good-enough answer found in reasonable time. It may not be the very best (optimal) answer, and the course accepts that trade when the exact method would take unreasonably long.

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.

Pause and think
A friend says, "Finding the best route through 60 cities is undecidable, because no computer could finish." What's wrong?
I thought about it. Show me
It's solvable, just unreasonably slow: an algorithm can check every route and would eventually give the right answer. That makes it a candidate for a heuristic, not an undecidable problem. Undecidable means no algorithm can answer correctly for every input, ever.
Count the steps
How many times does count ← count + 1 run in each segment, for n = 8? (a) REPEAT n TIMES { count ← count + 1 } (b) the nested loop above (c) REPEAT UNTIL (n ≤ 1) { n ← n / 2 ; count ← count + 1 }, starting from n = 64 instead. Which grow reasonably?
  1. (a) Once per pass: 8 times. Linear: doubling n doubles the work.
  2. (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.
  3. (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.
  4. 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
  1. For (a), how many passes?
  2. For (b), multiply outer passes by inner passes.
  3. For (c), halve 64 until you reach 1 and count the halvings.
Check yourself
Which problem is undecidable?
  1. ADeciding whether a whole number is prime
  2. BFinding the shortest route through 50 cities
  3. CDeciding, for every possible program and input, whether the program will eventually stop
  4. 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.

Check yourself
An algorithm's number of steps doubles every time one item is added to its input. Which statement is true?
  1. AIt runs in polynomial time, so it is reasonable for large inputs.
  2. BIt runs in exponential time, so a heuristic may be needed for large inputs.
  3. CThe problem it solves must be undecidable.
  4. 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.