3.17 Algorithmic Efficiency

Measuring Efficiency

Algorithmic efficiency describes how the runtime (or memory use) of an algorithm grows as input size increases. We don't measure exact seconds—that depends on hardware. Instead, we count how the number of steps scales with input size, letting us compare algorithms independent of the computer running them.

Efficient vs. Inefficient Algorithms

An efficient algorithm solves a problem in a reasonable amount of time even as input grows large (e.g., linear or logarithmic growth). An inefficient algorithm takes drastically more time as input grows (e.g., exponential or factorial growth), becoming impractical for large inputs even on fast computers.

Reasonable Time & Heuristics

A reasonable time algorithm's runtime grows proportionally (polynomially) with input size. Undecidable problems have no algorithm that solves them in all cases. For unsolvable-in-reasonable-time problems, programmers use heuristics—strategies that find a good, though not always optimal, solution quickly.

Key terms

Algorithmic efficiency

How the runtime or memory use of an algorithm scales as input size increases.

Efficient algorithm

An algorithm whose runtime grows reasonably (e.g., linearly) as input size increases.

Inefficient algorithm

An algorithm whose runtime grows drastically (e.g., exponentially) as input size increases, becoming impractical for large inputs.

Undecidable problem

A problem for which no algorithm can correctly solve every possible input.

Heuristic

A problem-solving strategy that quickly finds a good, though not necessarily optimal, solution.

Try an AP-style question

Which describes an algorithm that runs in reasonable time?

1. It never finishes
2. Its steps grow exponentially (e.g., 2ⁿ)
3. It needs infinite memory
4. Its steps grow polynomially (e.g., n²)