Recap
- A problem is a general task; an instance has specific input.
- A decision problem has a yes/no answer; an optimization problem seeks the best solution.
- Efficiency: an estimate of resources used, as a function of input size; measure informally by counting how many times statements execute.
- Different correct algorithms for one problem can differ greatly in efficiency.
- Reasonable time: polynomial or slower growth (constant, linear, square, cube).
- Unreasonable time: exponential and factorial growth.
- A heuristic gives a solution that is not guaranteed optimal; used when exact methods are impractical.
- Formal analysis (Big-O) is not required.
Key relationships
| Growth | Steps for n = 20 | Reasonable? |
|---|---|---|
| Constant | 1 | Yes |
| Linear n | 20 | Yes |
| Square n² | 400 | Yes |
| Cube n³ | 8,000 | Yes |
| Exponential 2n | 1,048,576 | No (for large n) |
| Factorial n! | 2,432,902,008,176,640,000 | No |
| Change | Effect |
|---|---|
| Double n, single loop | Work doubles |
| Double n, loop inside loop | Work quadruples |
| Add 1 to n, 2n algorithm | Work doubles |
| Faster computer | Does not change the growth pattern |
Assumptions
- Each simple statement counts as one step.
- Input size n is the number of items processed.
- “Reasonable” and “unreasonable” refer to growth with n, not to one particular run.
Method for comparing two algorithms
- Choose an input size, say n = 10, and count how many times the key statement runs for each algorithm.
- Double n and count again.
- See how the counts grow: doubling, quadrupling, or much faster?
- State which grows more slowly, and whether either is exponential or factorial.
Mistakes to avoid
- Counting lines of code instead of executions.
- Forgetting that nested loops multiply.
- Thinking a faster computer solves exponential growth.
- Calling a heuristic answer “optimal”.
- Confusing unreasonable time with impossible (undecidable).
Worked mini-example
A loop runs n times, and inside it an inner loop also runs n times. For n = 8 the inner statement runs 8 × 8 = 64 times. For n = 16 it runs 16 × 16 = 256 times: doubling n made the work four times bigger.
Quick self-check
- Is “What is the cheapest route through all these towns?” a decision or optimization problem?
- An algorithm needs 2n steps. What happens to the steps when n goes from 40 to 41?
- Name one situation where a heuristic is appropriate.
Answers
- Optimization: it asks for the best (cheapest) solution.
- They double.
- When an exact algorithm would take an unreasonable time, such as finding the best tour of many towns, and an approximate answer is acceptable.
Where marks are won and lost
Typical questions give two or three code segments and ask which runs the most statements, or how the number of steps changes when the input doubles. Others ask whether a described algorithm runs in reasonable time, or when a heuristic is appropriate. Count executions carefully: a loop inside a loop multiplies the work. Remember that unreasonable time and impossibility (Topic 3.18) are different ideas.
Back to the full study guide for worked examples and explanations.