What is Algorithm Efficiency?
The efficiency of an algorithm describes how well it performs as the size of the input (n) grows. An efficient algorithm does more work with fewer comparisons, steps, or memory usage.
At IGCSE level, you compare algorithms by counting the maximum number of comparisons (or steps) for a given n.
Comparing the Four Key Algorithms
| Algorithm | Type | Max comparisons (n items) | Requires sorted? |
|---|
| Linear search | Searching | n | No |
| Binary search | Searching | log₂(n) | Yes |
| Bubble sort | Sorting | ~n²/2 (n−1 passes) | No |
| Merge sort | Sorting | ~n × log₂(n) | No |
In practice — concrete examples
| n | Linear search | Binary search | Bubble sort | Merge sort |
|---|
| 8 | 8 | 3 | 28 | ~24 |
| 16 | 16 | 4 | 120 | ~64 |
| 1,000 | 1,000 | ~10 | ~500,000 | ~10,000 |
| 1,000,000 | 1,000,000 | ~20 | ~5×10¹¹ | ~20,000,000 |
Choosing the Right Algorithm
The best algorithm to use depends on:
- Size of data: for small datasets, even an inefficient algorithm is fast enough. For large datasets, efficiency matters greatly.
- Whether data is sorted: if already sorted, binary search is ideal. If unsorted, sorting first (then binary searching) may be worth it only if you will search many times.
- How often you search: if searching only once, a linear search may be simpler. If searching many times, sorting first (for binary search) saves time overall.
Sorted vs Unsorted — the tradeoff
Suppose you have 1,000 items and need to find one value:
- Linear search (unsorted): ~1,000 comparisons
- Sort first (bubble: ~500,000) then binary search (~10): ~500,010 comparisons total — WORSE!
- But if you search 1,000 times: linear = 1,000,000 vs sort once then binary × 1,000 = 500,000 + 10,000 = 510,000 — sorting first wins!
Summary Comparison
| Linear Search | Binary Search | Bubble Sort | Merge Sort |
|---|
| Efficiency | Low (large n) | High | Low (large n) | High |
| Data must be sorted? | No | Yes | No | No |
| Extra memory needed? | Minimal | Minimal | Minimal (temp) | Yes |
| Complexity to code | Simple | Moderate | Simple | Complex |
| Best for | Small/unsorted data | Large sorted data | Small data | Large data |
Exam tip: Cambridge often asks you to "justify your choice of algorithm" — always state WHY (e.g., "binary search is more efficient as it halves the search space on each step, so it needs only log₂(n) comparisons rather than n"). Simply naming an algorithm without justification usually loses marks.
⚠️ Common Mistakes
- Saying "binary search is better" without explaining WHY (fewer comparisons, halving the search space)
- Confusing efficiency with speed — efficiency is about how comparisons scale with n, not absolute speed
- Thinking merge sort always needs fewer comparisons than bubble sort for ALL inputs — for very small n, bubble sort may actually be faster in practice due to lower overhead