Skip to topic
    ← Back to course topics

    Order of complexity — AQA A-Level Computer Science

    Order of complexity evaluates algorithm efficiency by defining how execution time and memory requirements scale as input size approaches infinity using Big-O notation. It distinguishes tractable polynomial-time problems from intractable exponential algorithms, enabling developers to choose optimal algorithms for large data sets.

    Order of complexity explained

    Big-O notation describes how the running time of an algorithm grows as the size of its input, usually written n, increases.

    Read the full explanation

    It ignores constant factors and lower-order terms, so an algorithm that performs 3n + 5 steps is described as O(n) because, for large n, the linear term dominates. To apply it, identify the dominant term of the step count and drop its coefficient. Common classes, from slowest-growing to fastest-growing, include O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic and O(2ⁿ) exponential. Compare two algorithms by their classes rather than by timing a single run, because the class shows behaviour for large inputs. The statement asks you to apply this to cases where running time grows in a given pattern, so practise matching a description of an algorithm to its class.

    Your focus

    1. Be familiar with Big-O notation to express time complexity and be able to apply it to cases where the running time requirements of the algorithm grow in:

    Which command word is this?

    Give the exact Big-O classification (e.g. O(n log n)) without providing working or descriptive justification.

    Order of complexity exam tips

    Topic Overview

    Order of complexity in AQA A-Level Computer Science formalizes the mathematical analysis of computational efficiency in terms of execution time and space memory. Using Big-O notation, students assess how resource consumption scales asymptotically as the input data set size n approaches infinity, independent of specific hardware or implementation details.

    This topic bridges theoretical computation with practical software engineering by categorizing problems into tractable polynomial classes and intractable exponential classes. Mastering complexity analysis enables candidates to rigorously justify algorithmic selection for searches, sorts, and graph traversals across both exam papers.

    Key Concepts
    • →Big-O notation represents the upper bound or worst-case growth rate of an algorithm as input size n grows indefinitely.
    • →Standard time complexity hierarchy in increasing order of growth: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).
    • →Space complexity measures the total auxiliary memory required by an algorithm relative to the input size during execution.
    • →Tractable problems have polynomial-time solutions (O(n^k)), whereas intractable problems require super-polynomial time (e.g. O(2^n)) and typically rely on heuristic methods for practical approximations.
    Marking Points
    • Expresses running time as a function of input size n before applying notation
    • Drops constant factors and lower-order terms when stating the Big-O class
    • Identifies the dominant term that determines growth for large n
    • Matches a growth pattern to the correct class such as O(n) or O(n²)
    • Explains that Big-O describes behaviour as input size increases rather than exact timing
    Examiner Tips
    • 💡Work from the step count to the dominant term, then drop the coefficient
    • 💡Memorise the common classes in order of growth so comparisons are quick
    • 💡Check your answer by asking which term dominates when n is very large
    • 💡When simplifying expressions, discard lower-order terms and constant coefficients; for example, 4n^2 + 12n + 8 simplifies strictly to O(n^2).
    • 💡Explicitly differentiate between worst-case and average-case performance when comparing sorting algorithms like Quicksort and Merge Sort.
    • 💡Reference the specific structure of algorithms, such as dividing the problem domain in half (logarithmic) or using nested iterations (quadratic).
    Common Mistakes
    • Treats Big-O as the exact number of operations; state the growth class, not a precise count
    • Keeps coefficients such as O(3n); remove them to write O(n)
    • Ranks growth incorrectly, for example placing O(n²) below O(n log n); compare the growth rates for large n
    • Believing Big-O measures execution duration in seconds rather than the rate of operation growth relative to input size.
    • Assuming intractable problems have no algorithmic solution at all, failing to recognize they are solvable in theory but computationally unfeasible for large inputs in polynomial time.
    • Thinking space complexity measures the size of the initial input array rather than the additional auxiliary memory created by the algorithm during execution.
    Revision Plan
    1. 1Week 1, Days 1-2: Memorise the standard complexity order hierarchy and practice graphing O(1) through O(n!).
    2. 2Week 1, Days 3-5: Analyse pseudocode blocks to identify nested loops, halving steps, and recursive branches to determine Big-O formulas.
    3. 3Week 2, Days 1-3: Map standard AQA algorithms (searches, sorts, tree/graph traversals) to their best, average, and worst-case time and space complexities.
    4. 4Week 2, Days 4-5: Practice past paper exam questions focusing on tractability, intractability, and heuristic methods for the Travelling Salesperson Problem.
    Exam Question Types
    • 📋Code analysis questions: Calculating the Big-O time or space complexity from given pseudocode or high-level algorithm snippets.
    • 📋Comparative algorithm questions: Comparing two sorting or searching techniques across time efficiency, auxiliary memory, and stability.
    • 📋Tractability and heuristic essay questions: Explaining why exponential algorithms become unusable at scale and how heuristics provide sub-optimal yet practical solutions.
    Command Word Expectations (AQA)
    State

    Give the exact Big-O classification (e.g. O(n log n)) without providing working or descriptive justification.

    Explain

    Provide clear reasoning detailing how the structure of the algorithm (e.g. repeated halving or nested loops) dictates its mathematical order of complexity.

    Compare

    Identify similarities and differences between two algorithms in terms of both worst-case and average-case time and space complexity.

    How Students Lose Marks (Examiner Pitfalls)
    Pitfall: Stating that Quicksort always runs in O(n log n) time without acknowledging its worst-case performance.
    ❌ Weak Answer (Loses Marks):Quicksort has a time complexity of O(n log n) because it uses divide and conquer.
    Example improved answer:Quicksort has an average-case time complexity of O(n log n), but its worst-case time complexity is O(n^2) when the pivot chosen is consistently the smallest or largest element in an already sorted list.
    Examiner Tip: Always specify whether you are stating best, average, or worst-case complexity, as AQA mark schemes penalise ambiguity.
    Pitfall: Confusing intractable problems with non-computable (undecidable) problems.
    ❌ Weak Answer (Loses Marks):An intractable problem is an algorithm that impossible for a computer to calculate or solve.
    Example improved answer:An intractable problem is one for which a theoretical algorithm exists, but no polynomial-time algorithm is known, meaning solving it takes exponential or factorial time (e.g. O(2^n) or O(n!)) and is practically impossible for large inputs.
    Examiner Tip: Clearly contrast tractable (polynomial time, O(n^k)) with intractable (super-polynomial, O(k^n) or O(n!)), and non-computable (no algorithm exists at all, such as the Halting Problem).
    Step-by-Step Worked Solutions

    Question: An algorithm processes an array of size n using two nested loops. The outer loop runs n times. The inner loop executes j = 1 to n times, doubling j on each iteration (j = j * 2). Determine the worst-case Big-O time complexity of this algorithm and justify your answer.

    1. 1.Step 1: Analyze the outer loop. The loop variable increments linearly from 1 to n, executing exactly n iterations, giving O(n) for the outer cycle.
    2. 2.Step 2: Analyze the inner loop. The loop control variable j starts at 1 and doubles each cycle until it exceeds n. The number of iterations k satisfies 2^k <= n, meaning k = log2(n). Thus, the inner loop executes in O(log n) time.
    3. 3.Step 3: Combine nested operations. Because the inner loop runs to completion for every single iteration of the outer loop, multiply the individual complexities: n * log2(n).
    4. 4.Step 4: Formalise Big-O notation by dropping constants and base notation to express the asymptotic upper bound.
    Final Answer: The worst-case time complexity is O(n log n).

    Question: An encryption key-cracking routine has a time complexity of O(2^n), where n is the key length in bits. If a key length of 30 bits takes 0.5 seconds to crack on a given system, calculate the theoretical time required to crack a 40-bit key on the same system.

    1. 1.Step 1: Identify the relationship between time T and input size n for O(2^n). T(n) = c * 2^n, where c is a constant.
    2. 2.Step 2: Calculate the scaling factor between n = 30 and n = 40: 2^40 / 2^30 = 2^(40 - 30) = 2^10 = 1024.
    3. 3.Step 3: Multiply the initial time by the scaling factor: T(40) = T(30) * 1024 = 0.5 seconds * 1024.
    4. 4.Step 4: State the final calculated value clearly with appropriate units.
    Final Answer: 512 seconds (or 8 minutes and 32 seconds).
    Active Recall Memory Test
    What is the worst-case time complexity of Merge Sort, and why does it not degrade like Quicksort?
    Key Fact: O(n log n). It consistently divides the list in half regardless of initial item ordering, avoiding degenerate unbalanced splits.
    What mathematical criterion defines an algorithm as tractable?
    Key Fact: It can be solved by a polynomial-time algorithm, denoted as O(n^k) where k is a constant.
    What is the worst-case space complexity of an in-place Bubble Sort compared to a recursive Merge Sort?
    Key Fact: Bubble Sort has O(1) auxiliary space complexity, whereas Merge Sort requires O(n) auxiliary space to hold split subarrays.
    Why are heuristic methods used for problems with O(2^n) or O(n!) complexity?
    Key Fact: They find an adequate, near-optimal solution within a reasonable polynomial timeframe when finding the exact solution is computationally intractable.
    Frequently Asked Questions
    What is the difference between time complexity and space complexity?
    Time complexity quantifies the number of computational operations executed relative to the input size n, reflecting how run time scales. Space complexity measures the amount of auxiliary memory or storage an algorithm requires during execution relative to n. An algorithm can be fast in time yet inefficient in space, such as Merge Sort requiring O(n) auxiliary space compared to Quicksort requiring O(log n) stack space.
    Why do we ignore constants and lower-order terms in Big-O notation?
    Big-O notation describes asymptotic behaviour as the input size n tends towards infinity. At extremely large values of n, higher-order terms dominate total execution time so heavily that constant multipliers and lower powers become negligible. For example, in 5n^2 + 100n, the 5n^2 term accounts for virtually all execution growth as n reaches millions, simplifying the classification strictly to O(n^2).
    What does O(1) constant time complexity mean in practice?
    O(1) means the execution time or memory footprint remains completely independent of the size of the data structure. Accessing an element in an array via an index, pushing onto a stack, or looking up a key in an uncollided hash table are O(1) operations. It does not mean the operation takes zero seconds, but rather that it takes the same amount of time whether the data set holds ten items or ten billion items.
    Is an intractable problem the same as an impossible problem?
    No, intractable problems are not impossible to solve. A theoretical algorithm exists that produces the correct solution, but its time complexity is exponential (e.g. O(2^n)) or factorial (e.g. O(n!)), meaning it cannot be solved within a reasonable timeframe for moderate to large inputs. In contrast, non-computable problems, such as the Halting Problem, cannot be solved by any computer algorithm regardless of time.
    How do heuristic algorithms help with intractable problems?
    Heuristic algorithms use rules of thumb, educated guesses, or approximation techniques to find a 'good enough' solution in a realistic polynomial timeframe. For problems like the Travelling Salesperson Problem, finding the absolute shortest route requires factorial time O(n!), which is intractable for large networks. A heuristic algorithm, such as the nearest-neighbour approach, finds a practical, near-optimal route within seconds.