| Algorithm | Type | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Linear Search | Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | Search | O(1) | O(log n) | O(log n) | O(1) |
| Bubble Sort | Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap Sort | Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
This overview table is your single most valuable memorization asset for the entire chapter — examiners frequently ask to "compare" 2-3 algorithms directly by time/space complexity. See dedicated pages for Binary Search, Merge Sort, Quick Sort, and Heap Sort for full mechanics.
2026, Paper I, Q5(a) (6 marks) — Why is Binary Search not suitable for an unsorted list?
Binary Search compares the target with the middle element and discards a half, relying on the guarantee that everything on one side is smaller (or larger) than the middle — a guarantee that only sortedness provides. On unsorted data, the target could be anywhere, so discarding a half based on one comparison can wrongly eliminate the half that actually contains it, producing an incorrect "not found" even when the value is present.
Key reasoning points:
2024, Paper I, Q6(a) (8 marks) — For the following data sets, which sorting algorithms would work well, and which would not?
a. 10 floating-point values b. 1,000 integers c. 1,000 names d. 100,000 integers in [0,1000] e. 100,000 integers in [0, 1 billion] f. 100,000 names g. 1 million floating-point values h. 1 million names i. 1 million integers, uniform distribution j. 1 million integers, non-uniform distribution
| Dataset | Good choice | Why |
|---|---|---|
| a. 10 floats | Insertion Sort | tiny n — O(n log n) overhead not worth it |
| b. 1,000 ints | Quick/Merge Sort | O(n log n) comfortably beats O(n²) at this size |
| c. 1,000 names | Merge/Quick Sort | comparison-based, string cost per-compare but manageable |
| d. 100,000 ints, range [0,1000] | Counting Sort | O(n+k), k=1000 is small — beats any comparison sort |
| e. 100,000 ints, range [0,1B] | Quick/Merge/Radix Sort | Counting Sort impractical — k too large |
| f. 100,000 names | Merge/Quick Sort | good pivot/median strategy avoids Quick Sort's worst case |
| g. 1M floats | Merge Sort / Introsort | scales well at this size |
| h. 1M names | Merge Sort (stable) or MSD Radix | guaranteed O(n log n), stability often wanted for names |
| i. 1M ints, uniform | Bucket Sort | uniform distribution is Bucket Sort's ideal case — near O(n) |
| j. 1M ints, non-uniform | Quick/Merge/Heap/Radix Sort | Bucket Sort degrades badly — buckets fill unevenly |
Key reasoning points: