Show understanding that different algorithms which perform the same task can be compared by using criteria (e.g. time taken to complete the task and memory used)
Show understanding that different algorithms which perform the same task can be compared by using criteria such as the time taken to complete the task and the memory used.
What is an algorithm?
An algorithm is a finite, well‑defined sequence of steps that solves a problem or performs a computation. It can be expressed in natural language, pseudocode, flowcharts or a programming language.
Why compare algorithms?
To choose the most efficient solution for a given problem.
To understand trade‑offs between speed and resource consumption.
To predict how a program will behave as the size of the input grows.
Criteria for comparison
The two principal criteria used in A‑Level Computer Science are:
Time complexity – how the running time grows with the size of the input, usually expressed using Big‑O notation.
Space (memory) complexity – how much additional memory the algorithm requires, also expressed with Big‑O notation.
Other secondary criteria (not examined in detail) include simplicity, ease of implementation, and stability (for sorting algorithms).
Big‑O notation (brief reminder)
Big‑O describes an upper bound on the growth rate of a function. Common classes are:
\$O(1)\$ – constant time
\$O(\log n)\$ – logarithmic time
\$O(n)\$ – linear time
\$O(n \log n)\$ – linearithmic time
\$O(n^2)\$ – quadratic time
\$O(2^n)\$ – exponential time
Example 1 – Searching a list
Consider the task of locating a target value in an unsorted list of \$n\$ numbers.
Linear Search
Algorithm: examine each element in turn until the target is found or the list ends.
Suggested diagram: flowchart of linear search.
Binary Search
Algorithm: repeatedly divide a sorted list in half, discarding the half that cannot contain the target.
Suggested diagram: binary search decision tree.
Comparison of searching algorithms
Algorithm
Pre‑condition
Worst‑case time
Average‑case time
Space (extra)
Linear Search
None
\$O(n)\$
\$O(n)\$
\$O(1)\$
Binary Search
List sorted in non‑decreasing order
\$O(\log n)\$
\$O(\log n)\$
\$O(1)\$ (iterative) or \$O(\log n)\$ (recursive)
Example 2 – Sorting a list
Sorting the same collection of \$n\$ numbers can be achieved by many different algorithms. Two common choices are Bubble Sort and Quick Sort.
Bubble Sort
Repeatedly steps through the list, swapping adjacent elements that are out of order. Simple to implement but inefficient for large \$n\$.
Quick Sort
Divides the list into two sub‑lists around a “pivot” element, then recursively sorts the sub‑lists. Generally much faster, but requires careful handling of the pivot to avoid worst‑case behaviour.
Comparison of sorting algorithms
Algorithm
Worst‑case time
Average‑case time
Best‑case time
Space (extra)
Stable?
Bubble Sort
\$O(n^2)\$
\$O(n^2)\$
\$O(n)\$
\$O(1)\$
Yes
Quick Sort
\$O(n^2)\$ (poor pivot choice)
\$O(n \log n)\$
\$O(n \log n)\$
\$O(\log n)\$ (recursive stack)
No (unless modified)
How to perform a comparison in an exam
Identify the task that both algorithms solve.
State the relevant input size variable (commonly \$n\$).
Give the time‑complexity for each algorithm in Big‑O form, citing worst‑case, average‑case and best‑case if required.
Give the space‑complexity, distinguishing between auxiliary memory and any memory used for input storage.
Discuss any additional factors that might affect the choice (e.g., stability, ease of implementation, typical input characteristics).
Conclude which algorithm is more appropriate for the given scenario, justifying the decision with the criteria above.
Key take‑aways
Algorithms that solve the same problem can differ dramatically in efficiency.
Time complexity measures how the running time scales with input size; space complexity measures additional memory usage.
Big‑O notation provides a language for comparing algorithms independent of hardware.
When comparing, always consider the context: input size, typical data distribution, and resource constraints.