Definition
An algorithm is suitable for a task when both its execution time and the memory it needs are acceptable for the amount of data and the way that data is arranged. Two algorithms that give the same result can differ greatly in both.
Time and Space Complexity of the Standard Algorithms
Key Point
| Algorithm | Best-case time | Average time | Worst-case time | Space |
|---|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) | O(1) |
| Binary search | O(1) | O(log n) | O(log n) | O(1) |
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
Choosing an Algorithm for a Task and Data Set
| Situation | Suitable algorithm | Reason |
|---|---|---|
| Searching data that is not in order | Linear search | A binary search only works on sorted data |
| Searching a large sorted list | Binary search | O(log n): about 20 comparisons for a million items |
| Sorting a short list, or one that is almost in order | Insertion sort or bubble sort | Close to O(n) on nearly sorted data, O(1) space and simple to write |
| Sorting a long list when memory is plentiful | Merge sort | O(n log n) in every case, but needs O(n) extra memory for the sublists |
| Sorting a long list when memory is limited | Quick sort | O(n log n) on average with little extra memory, but O(n²) if the pivots are badly chosen |
| Shortest path when the distance left can be estimated | A* algorithm | The heuristic means fewer nodes are visited than with Dijkstra's algorithm |
Worked Example
How the Number of Steps Grows With n
The figures are worst-case numbers of comparisons or steps. With 16 items the choice of algorithm makes little difference. With a million items a bubble sort needs roughly 50,000 times as many steps as a merge sort, and a linear search roughly 50,000 times as many comparisons as a binary search.
| Items (n) | Binary search O(log n) | Linear search O(n) | Merge sort O(n log n) | Bubble sort O(n²) |
|---|---|---|---|---|
| 16 | 5 | 16 | 64 | 256 |
| 1,024 | 11 | 1,024 | about 10,000 | about 1 million |
| 1,048,576 | 21 | 1,048,576 | about 21 million | about 1 million million |
Exam Tip
When comparing algorithms, give the Big O for both time and space and link each to the data in the question: how many items there are, whether they are already in order and how much memory is available.