1.2.7 Algorithm efficiency and evaluation
What Is Algorithm Efficiency?
An algorithm is efficient if it solves its problem correctly using as few resources as possible — primarily time (number of operations) and memory (storage used). When multiple correct algorithms exist for the same problem, the most efficient one is preferred, especially as data sizes grow.
Efficiency is evaluated using logical reasoning and test data — not just by measuring real execution time, which depends on hardware.
Measures of Efficiency
The number of comparisons an algorithm makes is a key measure of its time efficiency. A comparison is any evaluation of a condition (e.g. a > b, nums[i] == target).
| Algorithm | Comparisons (worst case, n items) |
|---|---|
| Linear search | n (check every element) |
| Binary search | log₂(n) (halve each time) |
| Bubble sort | approximately n² / 2 |
| Merge sort | approximately n × log₂(n) |
Concrete comparison: n = 1024
- Linear search: up to 1024 comparisons
- Binary search: at most 10 comparisons (log₂1024 = 10)
- Bubble sort: approximately 524,288 comparisons
- Merge sort: approximately 10,240 comparisons
The number of passes through a loop directly determines how many times the loop body executes. Fewer passes = less work = more efficient.
# Algorithm A: one loop — n passes
for i in range(n):
process(i)
# Algorithm B: nested loops — n × n passes
for i in range(n):
for j in range(n):
process(i, j)Algorithm B does n² operations for the same n; it becomes dramatically slower as n grows. Reducing nested loops or exiting loops early (once a target is found) both improve efficiency.
Memory use is the second dimension of efficiency. Some algorithms use only the original data structure (in-place); others require additional storage.
- Bubble sort: sorts in place — no additional list needed, low memory use.
- Merge sort: creates new sub-lists during splitting and merging — additional memory proportional to n is required.
For large datasets, memory efficiency can be just as important as time efficiency — a faster algorithm that requires twice as much memory may be impractical on a device with limited RAM.
Fitness for Purpose
An algorithm is fit for purpose if it correctly solves the problem for all valid inputs, including edge cases. Evaluating fitness for purpose uses structured test data:
| Test type | Description | Example (age input, valid 0–120) |
|---|---|---|
| Normal | Typical, expected input | 25 |
| Boundary | Values at the exact limits | 0, 1, 119, 120 |
| Erroneous | Invalid input the program should reject | -1, 121, "hello" |
A good algorithm handles all three categories correctly. Boundary testing is especially important as errors often occur at the edges of conditions (e.g. using > instead of >= means value 0 would fail when it should pass).
Key Takeaways
- Efficiency is measured by number of comparisons, loop passes and memory use.
- Binary search is far more efficient than linear search for large sorted data.
- Merge sort is more efficient than bubble sort for large lists but uses more memory.
- Fitness for purpose = correctly handles normal, boundary and erroneous inputs.