Understand Big-O notation for time and space complexity, the common orders of growth, how to determine the complexity of an algorithm, and the meaning of best, average and worst case.

What this dot point is asking

AQA wants you to use Big-O notation to express the time and space complexity of an algorithm, recognise the common orders of growth, work out an algorithm's complexity from its structure, and explain best, average and worst case.

What Big-O measures

Time complexity measures how the number of operations grows; space complexity measures how the additional memory used grows. The reason constants are dropped is that they depend on the hardware and the language, whereas the order of growth is an intrinsic property of the algorithm. For large enough $n$, an $O(n \log n)$ algorithm always beats an $O(n^2)$ one regardless of constant factors, which is what makes Big-O a fair comparison.

The common orders of growth

To get a feel for the gap: at $n = 1000$, an $O(n)$ algorithm does about 1000 steps, an $O(n \log n)$ one about 10 000, an $O(n^2)$ one about a million, and an $O(2^n)$ one a number with hundreds of digits. This is why exponential algorithms are described as intractable: doubling the input size squares the work.

Determining complexity, and best/worst case

To find complexity, identify how many times the dominant operation runs in terms of $n$. A single loop over $n$ items is $O(n)$; a loop nested inside another is $O(n^2)$; repeatedly halving gives $O(\log n)$. Constants and lower-order terms are dropped, so $3n + 5$ is $O(n)$ and $n^2 + n$ is $O(n^2)$.

The best case is the fewest operations (for example the target found first), the worst case is the most (target last or absent), and the average case is the expected behaviour over typical inputs. Big-O usually quotes the worst case because it guarantees an upper bound on the running time, which is what matters when you need a guarantee that the algorithm will finish in time.

Space complexity is measured the same way but counts additional memory rather than operations. An in-place algorithm such as bubble sort uses only a constant amount of extra space, so it is $O(1)$ in space; merge sort allocates temporary sublists proportional to the input, so it is $O(n)$ in space. Recursive algorithms also consume memory on the call stack, one frame per level of recursion, so a recursion that goes $n$ levels deep has $O(n)$ space complexity even if it appears to use little memory in its body. This is why an algorithm can be excellent on time but unacceptable on memory, and why the specification asks you to consider both dimensions.

A common exam skill is reading complexity straight from a structure without running it. A loop that increments a counter by one each time runs $O(n)$ times; a loop that doubles or halves a variable each time runs $O(\log n)$ times; two independent loops run one after the other add, giving the dominant of the two; loops nested inside each other multiply, giving a product. Recognising these patterns lets you classify most exam algorithms in a few seconds, which is the intended outcome of this part of the specification.