Evaluating Algorithms
The final lesson: bringing it all together. Learn to compare algorithms objectively using Big-O notation, apply a structured framework for choosing between search and sort algorithms, and tackle the most challenging exam questions in this series.
Knowing how to write a sorting algorithm is useful. Knowing which sorting algorithm to use - and being able to justify your choice with evidence - is what separates good software design from great software design. In real development teams, algorithm choice decisions are made by arguing from efficiency data, not from gut feeling. This lesson gives you the conceptual tools to make and justify those decisions.
Big-O notation describes how the number of operations grows as the input size n increases. It captures the dominant term and ignores constants - we do not care whether an algorithm takes 3n or 5n operations; both are O(n) because they grow at the same rate.
Big-O tells us the order of growth, not the exact number of steps. It answers the question: "If I double the input size, how much more work does the algorithm do?"
| Complexity | Name | Double n does what? | n=10 | n=100 | n=1000 | Example |
|---|---|---|---|---|---|---|
| O(1) | Constant | No change | 1 | 1 | 1 | Array access by index |
| O(log n) | Logarithmic | +1 step | 3-4 | 7 | 10 | Binary search |
| O(n) | Linear | 2x work | 10 | 100 | 1,000 | Linear search |
| O(n log n) | Log-linear | ~2x work | 33 | 664 | 9,966 | Merge sort |
| O(n2) | Quadratic | 4x work | 100 | 10,000 | 1,000,000 | Bubble/insertion sort |
For small inputs (n < 50), all these complexities look similar and the choice barely matters. For large inputs, the differences are enormous. Sorting 1,000,000 items:
O(n log n) = ~20,000,000 operations
O(n2) = 1,000,000,000,000 (one trillion) operations
A modern computer can do about 1 billion operations per second. O(n log n) takes 0.02 seconds. O(n2) takes 16 minutes. This is why choosing the right algorithm matters enormously for real applications.
| Algorithm | Type | Best case | Worst case | Sorted input required? | Key advantage |
|---|---|---|---|---|---|
| Linear search | Search | O(1) | O(n) | No | Works on any list |
| Binary search | Search | O(1) | O(log n) | Yes | Extremely fast for large sorted lists |
| Bubble sort | Sort | O(n)* | O(n2) | No | Simple to understand and implement |
| Insertion sort | Sort | O(n) | O(n2) | No | Efficient for nearly-sorted or small lists |
| Merge sort | Sort | O(n log n) | O(n log n) | No | Consistent performance for large lists |
* Bubble sort best case O(n) only with early termination optimisation enabled.
The most-tested evaluation questions are:
1. "Compare algorithm X and algorithm Y for a given scenario" - always discuss both best and worst case, and any requirements (e.g. sorted list).
2. "Which algorithm would be most suitable and why?" - always give a specific reason tied to the scenario (e.g. "the list is already sorted so binary search is appropriate").
3. "State the maximum number of comparisons for algorithm X on n items" - know: linear search = n, binary search = log2(n), bubble sort pass 1 = n-1.
4. "State one disadvantage of bubble sort compared to merge sort" - O(n2) vs O(n log n) worst case.
Answer the questions below and we will recommend the most appropriate algorithm.
Binary search worst case: log2(2000) = approximately 11 comparisons.
Linear search worst case: 2,000 comparisons.
Since the list is already sorted alphabetically, binary search can be used. It is significantly more efficient, requiring at most 11 comparisons to find any name, compared to up to 2,000 for linear search. For a receptionist performing many lookups throughout the day, this efficiency improvement is valuable.
[Award 1 mark for identifying binary search, 1 mark for stating it requires a sorted list (which is satisfied), 1 mark for the complexity comparison or numbers, 1 mark for a clear justification.]
Insertion sort is an online algorithm - it can sort data as it arrives one element at a time without needing to restart the sort. When a new score is added, it is simply inserted into its correct position in the already-sorted list. The list of 500 items is also small enough that O(n2) worst-case performance is acceptable.
[Award 1 mark for naming insertion sort, 1 mark for explaining it handles one-at-a-time data (online algorithm), 1 mark for noting it is suitable for small lists or nearly-sorted data.]
Bubble sort advantage: Bubble sort is simpler to understand, implement and trace. It is also an in-place algorithm (requires only O(1) extra memory), whereas merge sort requires additional memory (O(n)) to store sub-lists during the merge phase. [1 mark for either point]
Answer: Maximum 9 comparisons. [1 mark for correct answer]
Note: If asked about n=1000, log2(1000) = 9.97, which rounds up to 10 comparisons maximum. Always round up for maximum comparisons.
Test yourself
1. An algorithm with O(n2) complexity is run on a list of 100 items and takes 1 second. Approximately how long would it take for a list of 200 items?
2. Which complexity grows most slowly as n increases?
3. A list is known to be in random (unsorted) order with 1,000,000 items. Which algorithm should be used to find a specific value?
4. State the worst-case complexity of merge sort.
5. An exam question asks "State one advantage of linear search over binary search." Which answer is correct?
You are designing a system to manage a music streaming library of 50 million songs. Users search by song title (very frequently - thousands of times per second). New songs are added daily. Existing songs are rarely removed. Discuss which search algorithm and which sort algorithm you would use, giving specific reasons based on the properties of each algorithm and the requirements of this system.
With 50 million songs and thousands of searches per second, efficiency is critical. Binary search has worst-case O(log n) = log2(50,000,000) = approximately 26 comparisons per search. Linear search would need up to 50,000,000 comparisons per search. At thousands of searches per second, binary search is the only feasible option. Requirement: the song list must be maintained in sorted order (by title).
Sort algorithm: Merge sort
When new songs are added daily, the list must be re-sorted. Merge sort is O(n log n) = approximately 1.3 billion operations for 50 million songs - fast and predictable. Bubble sort or insertion sort would require O(n2) = 2.5 quadrillion operations - completely infeasible. Insertion sort would be efficient if adding only a few songs to an already-sorted list (insert one at a time into the correct position), but merge sort handles bulk additions better.
Alternative approach: Maintain the list in a sorted data structure (like a balanced binary tree) so that insertion keeps it sorted automatically without a separate sort step. This is what real database systems do.
Practice what you have learned
Three levelled worksheets. Download, print and complete offline.