19.1 Algorithms – Comparing Different Solutions
Learning objective
Show that algorithms which solve the same problem can be compared by using appropriate criteria – principally time taken (running‑time) and memory used (auxiliary space). The comparison must be expressed using the terminology and notation required by the Cambridge International AS & A Level Computer Science (9618) syllabus.
1. What is an algorithm?
- A finite, well‑defined sequence of steps that produces a correct result for every allowed input and then terminates.
- Can be described in natural language, pseudocode, flowcharts or a programming language.
- Key properties required by the syllabus:
- Correctness – produces the right output.
- Finiteness – the process ends after a limited number of steps.
- Determinism – each step is unambiguous.
2. Why compare algorithms?
- To select the most efficient solution for a given problem.
- To understand trade‑offs between speed (time) and resource consumption (space).
- To predict how a program behaves as the size of the input grows (scalability).
- To justify the choice of one algorithm over another in an exam answer (Assessment Objective 2).
3. Criteria for comparison
- Time complexity – how the running time grows with the size of the input, expressed with Big‑O notation.
- Space (memory) complexity – how much extra memory the algorithm needs, also expressed with Big‑O.
- Secondary criteria (not examined directly but useful for discussion):
- Simplicity / ease of implementation
- Stability (for sorting algorithms)
- Recursion depth or need for a sorted input
- Typical data‑set characteristics (e.g., already‑sorted, small n)
4. Quick reminder of Big‑O notation
Big‑O gives an upper bound on the growth rate of a function, ignoring constant factors and lower‑order terms. The most common classes required by the syllabus are listed below.
| Class | Typical behaviour | Typical example |
|---|
| O(1) | Constant time – independent of input size | Accessing an array element |
| O(log n) | Logarithmic – halves the problem each step | Binary search |
| O(n) | Linear – examines each element once | Linear (sequential) search |
| O(n log n) | Linear‑logarithmic – divide‑and‑conquer sorts | Merge sort, heapsort |
| O(n²) | Quadratic – nested loops over the same data | Bubble sort, insertion sort (worst case) |
| O(2ⁿ) | Exponential – solution space doubles each step | Naïve recursive travelling‑salesman |
5. How to compare two algorithms (exam checklist)
- Identify the problem both algorithms solve.
- State the input‑size variable (normally n).
- Give the time‑complexity for each algorithm (worst‑case; mention average‑ and best‑case if relevant).
- Give the space‑complexity (auxiliary memory only – the input itself is not counted).
- Briefly discuss any secondary factors that could influence the choice (e.g., stability, recursion depth, pre‑conditions).
- Conclude which algorithm is more appropriate for the given scenario, linking the decision to the criteria above.
6. Example 1 – Searching a list
Task: locate a target value in a list of n numbers.
6.1 Linear (sequential) search
for i ← 0 to n‑1
if list[i] = target then return i
return NOT_FOUND
- Pre‑condition: none – works on unsorted data.
- Time complexity: O(n) worst‑ and average‑case; O(1) best case (target is first element).
- Space complexity: O(1) (loop counter and a temporary variable).
6.2 Binary search (iterative)
low ← 0; high ← n‑1
while low ≤ high
mid ← (low + high) div 2
if list[mid] = target then return mid
else if list[mid] < target then low ← mid + 1
else high ← mid – 1
return NOT_FOUND
- Pre‑condition: list must be sorted in non‑decreasing order.
- Time complexity: O(log n) in worst, average and best case.
- Space complexity:
- Iterative version – O(1).
- Recursive version – O(log n) (stack depth).
6.3 Comparison of the two search algorithms
| Algorithm | Pre‑condition | Worst‑case time | Average‑case time | Best‑case time | Space (extra) |
|---|
| Linear search | None | O(n) | O(n) | O(1) | O(1) |
| Binary search (iterative) | Sorted list | O(log n) | O(log n) | O(log n) | O(1) |
| Binary search (recursive) | Sorted list | O(log n) | O(log n) | O(log n) | O(log n) |
7. Example 2 – Sorting a list
Task: arrange n numbers in non‑decreasing order. Four algorithms are compared because they illustrate the full range of complexities required by the syllabus.
7.1 Bubble sort (simple, stable)
repeat
swapped ← false
for i ← 0 to n‑2
if a[i] > a[i+1] then
swap a[i], a[i+1]
swapped ← true
until not swapped
- Time: O(n²) worst & average, O(n) best (already sorted).
- Space: O(1) auxiliary.
- Stable: Yes.
7.2 Insertion sort (good for small or nearly sorted data)
for i ← 1 to n‑1
key ← a[i]
j ← i‑1
while j ≥ 0 and a[j] > key
a[j+1] ← a[j]
j ← j‑1
a[j+1] ← key
- Time: O(n²) worst & average, O(n) best.
- Space: O(1) auxiliary.
- Stable: Yes.
7.3 Quick sort (fast on average, not stable)
function quickSort(a, low, high)
if low < high then
p ← partition(a, low, high) // pivot ends in correct place
quickSort(a, low, p‑1)
quickSort(a, p+1, high)
- Time: O(n²) worst (poor pivot), O(n log n) average, O(n log n) best.
- Space: O(log n) auxiliary on average (recursion stack); O(n) worst.
- Stable: No (unless a specialised version is used).
7.4 Merge sort (stable, guaranteed O(n log n))
function mergeSort(a)
if length(a) ≤ 1 then return a
mid ← floor(length(a)/2)
left ← mergeSort(a[0 … mid‑1])
right ← mergeSort(a[mid … end])
return merge(left, right)
- Time: O(n log n) in worst, average and best cases.
- Space: O(n) auxiliary (temporary arrays for merging).
- Stable: Yes.
7.5 Comparison of common sorting algorithms
| Algorithm | Worst‑case time | Average‑case time | Best‑case time | Space (extra) | Stable? |
|---|
| Bubble sort | O(n²) | O(n²) | O(n) | O(1) | Yes |
| Insertion sort | O(n²) | O(n²) | O(n) | O(1) | Yes |
| Quick sort | O(n²) | O(n log n) | O(n log n) | O(log n) (stack) – O(n) worst | No |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
8. Using the comparison in an exam (AO2 – 6‑8 marks)
A concise, structured answer should contain the following points:
- State the task – e.g. “Both algorithms sort a list of n integers.”
- Identify the input variable – n (number of elements).
- Give the time‑complexities – worst‑case (mandatory), average‑case if asked, best‑case where relevant.
- Give the space‑complexities – auxiliary memory only.
- Discuss any secondary factors – stability, recursion depth, need for a sorted input, typical data size, ease of implementation.
- Conclude – clearly state which algorithm is preferable for the scenario and why, linking back to the criteria.
Use precise terminology (e.g., “O(n log n) time, O(1) extra space”) and avoid vague statements such as “faster” without justification.
9. Key take‑aways
- Algorithms that solve the same problem can differ dramatically in efficiency.
- Time complexity describes how running time grows with input size; space complexity describes extra memory required.
- Big‑O notation provides a hardware‑independent way to compare algorithms – a requirement of the Cambridge syllabus.
- When comparing, always consider the context: size of n, pre‑conditions (sorted data, limited memory), and any secondary requirements such as stability.
- In an exam, a well‑structured answer that explicitly states both criteria and draws a justified conclusion earns full marks.