Skip to topic
    ← Back to course topics

    Maths for understanding Big-0 notation — AQA A-Level Computer Science

    Big-O notation is a mathematical formalism used in Computer Science to classify algorithms according to how their run time or space requirements grow as the input size n approaches infinity. Mastering this topic requires evaluating dominant terms, applying base-2 logarithms to divide-and-conquer structures, and calculating worst-case growth rates independently of hardware performance.

    Maths for understanding Big-0 notation explained

    This statement asks you to understand a function as a rule that assigns to each input exactly one output.

    Read the full explanation

    The set of allowed inputs is the domain; the set from which outputs are drawn is the co-domain. In the example ℕ → ℕ, both domain and co-domain are the natural numbers, so the function takes a natural number and returns a natural number. For instance, f(n) = 2n maps 3 to 6 and 5 to 10, and every output is a natural number. Note that the co-domain is the set outputs are drawn from, not necessarily the set actually reached; the function f(n) = 2n never produces an odd number, though odd numbers belong to ℕ. Understanding this mapping is essential later, because Big-O notation describes how a function that gives running time or memory use relates the size of an input to the number of steps needed. Check that you can name the domain and co-domain of any given function.

    Your focus

    1. Be familiar with the mathematical concept of a function as a mapping from one set of values, the domain, to another set of values, drawn from the co-domain, for example ℕ → ℕ .

    Which command word is this?

    Provide a concise Big-O expression (e.g., 'O(n log n)') without requiring mathematical derivation or extended narrative justification.

    Maths for understanding Big-0 notation exam tips

    Topic Overview

    The mathematical foundations of Big-O notation provide computer scientists with a rigorous framework to quantify algorithmic efficiency independently of physical hardware, operating systems, or programming languages. By using asymptotic analysis, students learn to focus on the limiting behaviour of functions as the problem size n grows arbitrarily large.

    Within the AQA A-Level specification, this topic underpins algorithm design, sorting routines, graph traversal, and the distinction between tractable and intractable problems. Understanding the algebra and logarithms behind Big-O allows students to evaluate trade-offs between execution speed and memory consumption accurately across real-world systems.

    Key Concepts
    • →Asymptotic upper bound: Big-O mathematically formalises the worst-case growth rate of an algorithm, describing an upper limit on resource usage as n tends to infinity.
    • →Logarithmic reductions (base 2): Repeatedly dividing problem sizes in half (such as binary search or divide-and-conquer partitioning) produces logarithmic growth O(log n) because 2^k = n implies k = log2(n).
    • →Dominance and simplification rules: When summing polynomial terms, lower-order terms (e.g., n versus n^2) and constant factors are discarded because their contribution becomes negligible as n approaches infinity.
    • →Permutations and factorial growth: Combinatorial problems such as the brute-force Travelling Salesperson Problem generate permutations evaluated by n!, representing intractable complexity classes distinct from polynomial ones.
    Marking Points
    • Defines a function as a mapping in which each element of the domain maps to exactly one element of the co-domain.
    • Identifies the domain as the set of permitted inputs and the co-domain as the set outputs are drawn from.
    • Correctly interprets ℕ → ℕ as a function whose inputs and outputs are natural numbers.
    • Distinguishes the co-domain from the set of actual outputs (the range).
    Examiner Tips
    • 💡When given an arrow notation such as ℕ → ℕ, read the left-hand set as the domain and the right-hand set as the co-domain.
    • 💡Test a candidate function by picking a sample input and checking that it gives exactly one output inside the co-domain.
    • 💡Remember that distinguishing co-domain from range is a common source of error, so check whether a question is asking about possible outputs or actual outputs.
    • 💡Memorise the standard hierarchy of complexity classes in ascending order: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).
    • 💡When asked to calculate time scaling, show the ratio (n_new / n_old) clearly before raising it to the power matching the algorithm's complexity order.
    • 💡In algorithm code analysis, count loop nesting levels carefully: consecutive loops add complexities (O(n) + O(n) = O(n)), whereas nested loops multiply them (O(n) * O(n) = O(n^2)).
    Common Mistakes
    • Confuses the domain with the co-domain; state that the domain is the input set and the co-domain is the output set.
    • Assumes the co-domain must be fully covered by the outputs; state that the co-domain is the set outputs are drawn from, while the actual outputs may form a smaller set.
    • Treats an element of the domain as mapping to several outputs; state that a function assigns exactly one output to each input.
    • Believing that an O(n^2) algorithm is always slower than an O(n) algorithm for all values of n. In reality, constant overheads can make O(n^2) faster for very small inputs; Big-O only dictates performance as n becomes sufficiently large.
    • Assuming that the base of a logarithm matters in Big-O. By the change-of-base formula, log_a(n) = log_b(n) / log_b(a); because 1 / log_b(a) is a constant scalar, all logarithmic bases belong to the same complexity class O(log n).
    • Equating best-case, average-case, and worst-case complexities directly to Big-O notation. While Big-O is predominantly used to denote the worst case in A-Level exams, it is technically an asymptotic upper bound applicable to any defined scenario.
    Revision Plan
    1. 1Stage 1: Review logarithmic and polynomial maths, practicing manual evaluation of powers of 2 and repeated division by 2.
    2. 2Stage 2: Plot the curves of standard Big-O functions on graph paper to visualise how O(n log n) diverges from O(n^2) as n expands.
    3. 3Stage 3: Deconstruct iterative and recursive code snippets into algebraic operation counts, practicing the removal of coefficients and non-dominant terms.
    4. 4Stage 4: Complete past AQA exam questions on execution time extrapolation and tractability classifications under timed conditions.
    Exam Question Types
    • 📋Code and loop analysis: Deducing the Big-O time or space complexity from a given pseudocode algorithm with nested iterations or recursive calls.
    • 📋Proportional scaling calculations: Calculating the new execution time or memory footprint when input size n increases by a given factor.
    • 📋Comparative evaluation: Comparing two algorithms (e.g., merge sort vs bubble sort) using mathematical complexity curves to justify design decisions for large datasets.
    Command Word Expectations (AQA)
    State

    Provide a concise Big-O expression (e.g., 'O(n log n)') without requiring mathematical derivation or extended narrative justification.

    Calculate

    Demonstrate clear numerical working showing the scaling factor and exponentiation steps to arrive at a final execution time or memory figure with units.

    Explain

    Set out the mathematical reasoning behind a complexity classification, such as identifying halving steps for logarithmic behaviour or loop nesting for quadratic behaviour.

    How Students Lose Marks (Examiner Pitfalls)
    Pitfall: Treating Big-O notation as an absolute measurement of execution speed in seconds or clock cycles rather than a measure of growth rate relative to input size.
    ❌ Weak Answer (Loses Marks):The algorithm has a time complexity of O(n^2) because it took 4 seconds to process 100 items on the server.
    Example improved answer:The algorithm has a time complexity of O(n^2) because the number of basic operations grows in proportion to the square of the input size n as n tends towards infinity, regardless of hardware execution speed.
    Examiner Tip: Always refer to how the number of operations or resource usage scales as the input size n increases, rather than referencing clock time or processor benchmarks.
    Pitfall: Failing to drop coefficients and non-dominant terms when formalising Big-O expressions from operational counts.
    ❌ Weak Answer (Loses Marks):The total operations count is 3n^2 + 5n + 12, so the Big-O complexity is O(3n^2 + 5n).
    Example improved answer:The algorithm executes f(n) = 3n^2 + 5n + 12 operations. In asymptotic analysis, as n approaches infinity, the n^2 term dominates and scalar multipliers become negligible, simplifying the complexity strictly to O(n^2).
    Examiner Tip: When deriving complexity from an algebraic expression, state the dominant term clearly and explicitly drop all constant multipliers and lower-order terms.
    Step-by-Step Worked Solutions

    Question: An algorithm processes a two-dimensional array of dimensions n by n using the following pseudo-code: FOR i = 1 TO n FOR j = 1 TO i x = x + 1 ENDFOR ENDFOR Show mathematically how the total number of additions relates to n, and state the time complexity in Big-O notation.

    1. 1.Step 1: Express the total number of operations as a summation. The outer loop runs n times, and for each iteration i, the inner loop executes i times: Total operations S = 1 + 2 + 3 + ... + n.
    2. 2.Step 2: Apply the arithmetic series formula: S = n(n + 1) / 2 = (n^2 + n) / 2 = 0.5n^2 + 0.5n.
    3. 3.Step 3: Apply the mathematical principles of Big-O notation by identifying the dominant term as n approaches infinity (n^2 dominates n) and removing the constant coefficient (0.5).
    Final Answer: The exact operation count is (n^2 + n)/2, which simplifies asymptotically to a time complexity of O(n^2).

    Question: An algorithm with time complexity O(n^2) takes 0.4 seconds to process an input size of n = 1,000. Assuming hardware performance remains constant, calculate the expected execution time when the input size increases to n = 5,000.

    1. 1.Step 1: Calculate the scaling factor k of the input size: k = n_new / n_old = 5,000 / 1,000 = 5.
    2. 2.Step 2: Apply the growth rate defined by the complexity class. For an O(n^2) algorithm, execution time scales by k^2: Scale factor = 5^2 = 25.
    3. 3.Step 3: Multiply the baseline execution time by the growth factor: Expected time = 0.4 seconds * 25 = 10.0 seconds.
    Final Answer: The expected execution time for an input size of 5,000 is 10.0 seconds.
    Active Recall Memory Test
    What is the Big-O time complexity of an algorithm whose operation count is expressed as f(n) = 7n^3 + 42n^2 + 100?
    Key Fact: O(n^3). Lower-order terms (42n^2, 100) and the constant multiplier (7) are discarded.
    Why does doubling the input size of an O(2^n) algorithm result in squaring its growth factor rather than doubling the runtime?
    Key Fact: Because 2^(2n) = (2^n)^2, meaning the runtime is squared, demonstrating exponential intractability.
    Which mathematical operation explains why divide-and-conquer algorithms like binary search have O(log n) complexity?
    Key Fact: Repeated division by 2, which corresponds to the inverse of exponentiation: log2(n) iterations until the sub-problem size reduces to 1.
    What is the difference between polynomial time complexity and exponential time complexity in terms of tractability?
    Key Fact: Polynomial time algorithms (e.g., O(n^k)) are considered tractable and practically solvable for large inputs, whereas exponential algorithms (e.g., O(2^n)) are intractable.
    Frequently Asked Questions
    Why do we ignore constant numbers and coefficients in Big-O notation?
    Big-O notation evaluates asymptotic behaviour, which means we examine what happens as the input size n approaches infinity. For massive values of n, multiplying by a constant factor such as 3 or adding 100 has a negligible impact on the overall rate of growth compared to the exponent of n. As a result, constants are dropped to focus strictly on the fundamental order of complexity.
    Why is the base of the logarithm omitted in O(log n)?
    In Computer Science, logarithms typically use base 2 because data structures and search algorithms frequently divide datasets into halves. However, mathematically, logarithms in different bases differ only by a constant multiplier due to the change of base rule: log_b(n) = log_a(n) / log_a(b). Because constant multipliers are discarded in asymptotic analysis, all logarithmic bases belong to the same class, written simply as O(log n).
    How do I calculate Big-O complexity from nested loops?
    To find the complexity of nested loops, multiply the number of iterations of the outer loop by the number of iterations of the inner loop. If the outer loop executes n times and the inner loop executes n times for each outer pass, the operations multiply: n * n = n^2, resulting in O(n^2). If the loops are separate (sequential rather than nested), you add their runtimes instead: n + n = 2n, which simplifies to O(n).
    What is the difference between O(n log n) and O(n^2)?
    O(n log n), often called linearithmic time, grows much slower than O(n^2) quadratic time as n becomes large. For example, if n = 1,000,000, n log2(n) is approximately 20,000,000 operations, whereas n^2 is 1,000,000,000,000 operations. This massive mathematical difference is why efficient divide-and-conquer algorithms like merge sort are preferred over simple quadratic algorithms like bubble sort for large datasets.
    Can an algorithm have a different space complexity compared to its time complexity?
    Yes, space complexity measures the additional memory an algorithm allocates relative to the input size, while time complexity measures the number of operations performed. For instance, an in-place bubble sort has a time complexity of O(n^2) because of its nested passes, but an auxiliary space complexity of O(1) because it sorts elements within the original array without allocating extra storage.