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
- 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
- 1Week 1, Days 1-2: Memorise the standard complexity order hierarchy and practice graphing O(1) through O(n!).
- 2Week 1, Days 3-5: Analyse pseudocode blocks to identify nested loops, halving steps, and recursive branches to determine Big-O formulas.
- 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.
- 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)
Give the exact Big-O classification (e.g. O(n log n)) without providing working or descriptive justification.
Provide clear reasoning detailing how the structure of the algorithm (e.g. repeated halving or nested loops) dictates its mathematical order of complexity.
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)
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.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.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.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.Step 4: Formalise Big-O notation by dropping constants and base notation to express the asymptotic upper bound.
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.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.Step 2: Calculate the scaling factor between n = 30 and n = 40: 2^40 / 2^30 = 2^(40 - 30) = 2^10 = 1024.
- 3.Step 3: Multiply the initial time by the scaling factor: T(40) = T(30) * 1024 = 0.5 seconds * 1024.
- 4.Step 4: State the final calculated value clearly with appropriate units.