Skip to topic
    ← Back to course topics

    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

    1. 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
    1. 1Day 1-3: Construct a definitive summary matrix detailing best, average, and worst time complexities plus space complexities for all AQA core algorithms.
    2. 2Day 4-6: Work through algebraic comparisons of nested loops and divide-and-conquer recurrences to derive Big-O classifications from raw pseudocode.
    3. 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)
    Compare

    Identify both similarities and differences between two algorithms across defined parameters (e.g. time, space, readability). Do not simply describe each algorithm in isolation.

    Justify

    Provide valid theoretical or mathematical reasons (e.g., worst-case scenarios, memory restrictions) supporting why one algorithm should be chosen over another.

    Evaluate

    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)
    Pitfall: Confusing execution run time measured in seconds with Big-O computational time complexity.
    ❌ Weak Answer (Loses Marks):Algorithm A is better because when I tested it on my laptop it ran in 0.02 seconds, whereas Algorithm B took 0.15 seconds.
    Example improved answer:Algorithm A has a lower order of time complexity, O(N log N), compared to Algorithm B, which is O(N^2). Physical run time varies with hardware, processor speed, and system load, whereas Big-O formalises the mathematical growth rate in operations as input size N tends towards infinity.
    Examiner Tip: Never refer to clock time or seconds unless the question explicitly asks for a benchmark; always frame algorithmic comparison around asymptotic operations and input size N.
    Pitfall: Neglecting space complexity when comparing sorting or searching routines.
    ❌ Weak Answer (Loses Marks):Merge sort is strictly better than quicksort because its worst-case is O(N log N) while quicksort is O(N^2).
    Example improved answer:While merge sort guarantees O(N log N) time complexity across all cases, it requires O(N) auxiliary space for temporary sub-lists. In contrast, in-place quicksort requires only O(log N) auxiliary stack space, making quicksort preferable when primary memory is severely constrained.
    Examiner Tip: Evaluate trade-offs holistically: consider best, average, and worst-case time complexities alongside auxiliary space requirements.
    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. 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. 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. 3.Step 3: Calculate the direct comparison between both approaches: 1,024 comparisons for linear search versus at most 11 comparisons for binary search.
    Final Answer: Linear search requires a maximum of 1,024 comparisons (O(N)), whereas binary search requires a maximum of 11 comparisons (O(log N)), demonstrating exponential efficiency gains on sorted datasets.

    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. 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. 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. 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. 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.
    Final Answer: Insertion Sort: Best Time O(N), Worst Time O(N^2), Auxiliary Space O(1). Merge Sort: Best Time O(N log N), Worst Time O(N log N), Auxiliary Space O(N). Insertion Sort wins on memory and nearly-sorted data; Merge Sort wins on large, unordered inputs.
    Active Recall Memory Test
    What is the worst-case time complexity and auxiliary space complexity of Merge Sort?
    Key Fact: Worst-case time complexity: O(N log N); Auxiliary space complexity: O(N).
    Under what condition does standard Quicksort exhibit its worst-case time complexity of O(N^2)?
    Key Fact: When the chosen pivot is consistently the extreme value (minimum or maximum), such as choosing the first element in an already sorted or reverse-sorted array.
    Why can an algorithm with O(1) space complexity still be unsuitable for high-throughput enterprise systems?
    Key Fact: Because its time complexity might be O(N^2) or exponential (O(2^N)), resulting in prohibitive latency despite zero auxiliary memory overhead.
    Which searching algorithm requires the dataset to be ordered prior to execution, and what is its average time complexity?
    Key Fact: Binary search requires an ordered dataset; its average time complexity is O(log N).
    Frequently Asked Questions
    Why is Big-O used to compare algorithms instead of measuring seconds?
    Measuring execution time in seconds depends heavily on hardware specifications, CPU clock speed, background operating system processes, and compiler optimisations. Big-O provides an objective, hardware-independent mathematical framework that describes how operations scale strictly as a function of input size N.
    Is an O(N log N) algorithm always better than an O(N^2) algorithm?
    Theoretically yes for large inputs, but not necessarily for small inputs. An O(N log N) algorithm often carries higher constant coefficient overheads due to recursive calls and memory allocation. When N is very small (e.g., N < 20), an O(N^2) algorithm like insertion sort often runs faster in practice.
    What is the difference between space complexity and auxiliary space?
    Total space complexity accounts for the memory used by the original input data plus any additional working memory. Auxiliary space refers exclusively to the extra temporary working memory allocated by the algorithm itself (such as recursive stack frames or temporary arrays). Exam comparisons focus primarily on auxiliary space.
    How do I choose between Quicksort and Merge Sort in an exam question?
    Check the constraints: Merge Sort is preferred if guaranteed worst-case performance (O(N log N)) or data stability is required, provided memory is abundant. Quicksort is preferred if memory is restricted, as its in-place partition uses only O(log N) stack space, provided the risk of rare O(N^2) worst-case performance is acceptable.
    Does code readability and maintainability count when comparing algorithms?
    Yes, AQA mark schemes acknowledge that real-world algorithm selection balances computational complexity against development time and code maintainability. A simple, easily debugged O(N^2) routine may be preferred over a complex O(N log N) algorithm if data sets are small and developer maintenance costs are high.