Comparing algorithms — AQA A-Level Computer Science
Comparing algorithms in AQA A-Level Computer Science involves evaluating time and space complexity using Big-O notation, alongside factors like code readability, implementation effort, and stability. Mastering order of growth enables students to scientifically determine the most resource-efficient algorithm for varying problem sizes.
Comparing algorithms explained
Algorithms that solve the same problem can be compared by describing how the number of steps (or amount of memory) they need grows as the input grows.
Read the full explanation
Complexity is therefore written as a function f(n), where n is the size of the problem, for example the number of items in a list to be sorted or the number of nodes in a graph. A linear search of a list of n items may need up to n comparisons, so its complexity is a function that grows in direct proportion to n. A binary search on a sorted list needs roughly log₂n comparisons, so its function grows far more slowly. The key idea is that comparison is made relative to n: we ask how the work changes as n becomes larger, not how long one run takes on one machine. This lets a programmer predict which algorithm will remain practical when the problem becomes large.
Your focus
- Understand that algorithms can be compared by expressing their complexity as a function relative to the size of the problem.
Which command word is this?
Identify both similarities and differences between two algorithms across defined parameters (e.g. time, space, readability). Do not simply describe each algorithm in isolation.
Comparing algorithms exam tips
Topic Overview
Comparing algorithms requires evaluating alternative computational solutions to the same problem using standardised theoretical criteria. AQA A-Level Computer Science focuses on formal asymptotic analysis, specifically time complexity (how operation counts scale with input size N) and space complexity (memory overhead during execution).
Beyond Big-O classifications, a complete evaluation incorporates contextual realities including best, average, and worst-case inputs, recursive overhead, algorithm stability, and practical constraints such as cache locality and developer maintenance costs. This foundational topic links abstract data structures to practical software optimisation.
Key Concepts
- →Big-O notation: Formal asymptotic bounds representing the upper limit of an algorithm's growth rate as input size N scales to infinity.
- →Time complexity vs Space complexity: Balancing CPU cycle operations against volatile memory footprint (auxiliary RAM or call stack frames).
- →Worst-case, average-case, and best-case analysis: Recognizing that data distributions (e.g. sorted vs inverted arrays) fundamentally alter performance profiles.
- →Empirical benchmarking vs theoretical analysis: Understanding why hardware-dependent wall-clock measurements cannot replace mathematical order of growth.
Marking Points
- Defines complexity as a function that describes how the number of steps or amount of resource changes with the size of the problem
- Identifies n as the size of the problem, such as the number of items in a list
- Compares two algorithms by how their functions grow as n increases
- Explains that a comparison based on a function is independent of the specific hardware or language used
Examiner Tips
- 💡When a question asks you to compare algorithms, state the function for each one and then say which grows more quickly as n increases
- 💡Always name the variable n and say what it represents in the problem being solved
- 💡Use simple examples such as linear search and binary search to illustrate how functions differ
- 💡Always state the base case or dataset scenario (e.g., 'already sorted', 'randomly distributed', or 'reverse sorted') when comparing algorithm efficiencies.
- 💡Express Big-O notation with clean mathematical notation: use capital 'O' followed by brackets containing N (e.g., O(N log N)), and avoid informal expressions like 'logarithmic time without the O'.
Common Mistakes
- Treats complexity as the actual time in seconds an algorithm takes; correct it by explaining that complexity describes how work grows with problem size, not a fixed time
- Compares algorithms using only one input size; correct it by considering how the function behaves as n becomes larger
- Refers to complexity as a single number rather than a function of n; correct it by stating the relationship between n and the work done
- Assuming an O(N) algorithm is always faster than an O(N^2) algorithm: For tiny values of N, low-order constants or overheads may make O(N^2) faster; Big-O only describes trends as N becomes arbitrarily large.
- Believing quicksort is strictly O(N log N): Quicksort degrades to O(N^2) when an unfavourable pivot (such as the smallest or largest item) is systematically selected from an already sorted list.
- Treating space complexity as the total program size: Auxiliary space complexity refers exclusively to the extra memory allocated by the algorithm during execution, excluding the original input storage.
Revision Plan
- 1Day 1-3: Construct a definitive summary matrix detailing best, average, and worst time complexities plus space complexities for all AQA core algorithms.
- 2Day 4-6: Work through algebraic comparisons of nested loops and divide-and-conquer recurrences to derive Big-O classifications from raw pseudocode.
- 3Day 7-10: Practice 6-mark and 9-mark evaluation questions requiring justified selection of algorithms for real-world scenarios under hardware constraints.
Exam Question Types
- 📋Comparative fill-in tables: Matrix questions where you complete missing time or space complexities for specific sorting or pathfinding algorithms.
- 📋Scenario-based justification (6-9 marks): Extended response requiring you to select and justify the superior algorithm based on specified data sizes and hardware limitations.
- 📋Code analysis and simplification: Determining the Big-O difference between an unoptimised nested-loop algorithm and an optimised hash table/divide-and-conquer alternative.
Command Word Expectations (AQA)
Identify both similarities and differences between two algorithms across defined parameters (e.g. time, space, readability). Do not simply describe each algorithm in isolation.
Provide valid theoretical or mathematical reasons (e.g., worst-case scenarios, memory restrictions) supporting why one algorithm should be chosen over another.
Review the benefits and drawbacks of alternative algorithms in context, culminating in a reasoned concluding judgment balanced against trade-offs.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: An array of 1,024 sorted customer IDs must be queried repeatedly. Compare the maximum number of key comparisons required to locate an element or confirm its absence using linear search versus binary search.
- 1.Step 1: Identify worst-case comparison formula for linear search. Linear search examines every element until a match is found or the list ends, requiring N comparisons. For N = 1024, maximum comparisons = 1,024.
- 2.Step 2: Identify worst-case comparison formula for binary search. Binary search halves the search space each step: floor(log2(N)) + 1 comparisons. For N = 1024, log2(1024) = 10, so maximum comparisons = 10 + 1 = 11 (or 10 if standard decision tree leaves check equality on final division).
- 3.Step 3: Calculate the direct comparison between both approaches: 1,024 comparisons for linear search versus at most 11 comparisons for binary search.
Question: A developer needs to sort an array of N integers. Two candidate algorithms are Insertion Sort and Merge Sort. Compare these two algorithms in terms of best-case time complexity, worst-case time complexity, and auxiliary space complexity.
- 1.Step 1: Define time complexities for Insertion Sort. Best case (already sorted array) is O(N) as each element is inspected once with no shifts. Worst case (reverse sorted) is O(N^2) due to nested passes and maximum item shifting.
- 2.Step 2: Define time complexities for Merge Sort. Best case is O(N log N) and worst case is O(N log N) because the list is recursively divided in half regardless of initial item order.
- 3.Step 3: Define space complexities. Insertion Sort operates in-place, requiring O(1) auxiliary space. Merge Sort requires dynamic sub-arrays or buffers during the merge phase, yielding O(N) auxiliary space.
- 4.Step 4: Synthesise the comparison. Insertion Sort is preferable for nearly-sorted or tiny datasets where memory is critical; Merge Sort scales predictably on large, arbitrary inputs.