Complexity and Big-O Notation

Two algorithms that both solve the same problem may differ drastically in how their running time grows as the input size increases. Big-O notation gives us a way to compare algorithms in terms of how their time (or space) requirements scale, independent of hardware speed or specific constant factors.

Motivating example — sorting 1 000 000 numbers:

• Bubble sort $O(n^2)$: roughly $10^{12}$ operations — would take hours on a modern CPU
• Merge sort $O(n\log n)$: roughly $2\times 10^7$ operations — completes in under a second

The difference is not in the hardware — it is in the algorithmic complexity.

Big-O notation describes the asymptotic upper bound on the growth rate of a function as $n\to \infty$. It ignores:

• Constant factors (multiplying by 2 or 100 does not change the class)
• Lower-order terms ($n^2+n$ is $O(n^2)$, not $O(n^2+n)$)

AQA requires knowledge of these growth functions:

Name	Formula	Example
Constant	$f(n)=c$	Accessing an array element by index
Logarithmic	$f(n)=\log n$	Binary search; each step halves the problem
Linear	$f(n)=n$	Linear search; reading every element once
Polynomial	$f(n)=n^k$	Bubble sort $O(n^2)$; matrix multiply $O(n^3)$
Exponential	$f(n)=k^n$	Brute-force password cracking; subset enumeration
Factorial	$f(n)=n!$	Brute-force travelling salesman (all permutations)

Growth comparison — relative speed for large $n$:

$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$

Plotting the lower classes against input size $n$ shows how steeply each one pulls away from the others as $n$ grows:

$n$	${\log }_{2}n$	$n$	$n^2$	$2^n$
10	3	10	100	1 024
100	7	100	10 000	$\approx 10^{30}$
1 000	10	1 000	1 000 000	too large

The five Big-O classes AQA requires:

$O(1)$ — Constant: running time does not depend on input size.

// Access the first element of an array — always one step
OUTPUT arr[1]

$O(\log n)$ — Logarithmic: input size is halved (or reduced by a constant factor) each step.

// Binary search — halves the search space each iteration

$O(n)$ — Linear: one operation per input element.

// Sum all elements of an array
total ← 0
FOR i ← 1 TO n
    total ← total + arr[i]
NEXT i

$O(n^k)$ — Polynomial: nested loops. Two nested loops → $O(n^2)$. Three → $O(n^3)$.

// Compare every pair of elements — O(n²)
FOR i ← 1 TO n
    FOR j ← 1 TO n
        IF arr[i] = arr[j] THEN ...
    NEXT j
NEXT i

$O(k^n)$ — Exponential: the work doubles (or multiplies) with each unit increase in $n$. Grows too fast to be practical beyond small inputs.

Rules for deriving Big-O:

1. Single loop over $n$ elements → $O(n)$
2. Two nested loops over $n$ → $O(n^2)$; $k$ nested loops → $O(n^k)$
3. Halving the input each step → $O(\log n)$
4. Sequential (non-nested) blocks: take the highest order — $O(n^2)+O(n)=O(n^2)$
5. Drop constant multipliers: $O(5n)=O(n)$

Worked examples:

Example 1 — what is the complexity of this code?

FOR i ← 1 TO n
    FOR j ← 1 TO n
        result ← result + arr[i] * arr[j]
    NEXT j
NEXT i

Two nested loops, each from 1 to $n$: the body executes $n\times n=n^2$ times → $O(n^2)$.

Example 2 — what is the complexity of this code?

FOR i ← 1 TO n
    OUTPUT arr[i]
NEXT i
FOR i ← 1 TO n
    total ← total + arr[i]
NEXT i

Two sequential loops each $O(n)$: total is $O(n)+O(n)=O(2n)=O(n)$.

Worked comparison — searching algorithms:

Algorithm	Best	Average	Worst
Linear search	$O(1)$	$O(n)$	$O(n)$
Binary search	$O(1)$	$O(\log n)$	$O(\log n)$
BST search	$O(1)$	$O(\log n)$	$O(n)$

Worked comparison — sorting algorithms:

Algorithm	Best	Average	Worst	Space
Bubble sort	$O(n)$*	$O(n^2)$	$O(n^2)$	$O(1)$
Merge sort	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$

*$O(n)$ best case with early-termination optimisation (see sorting algorithms lesson).

For large $n$, an $O(n\log n)$ algorithm is always faster than an $O(n^2)$ algorithm in the long run, regardless of constant factors.

Big-O applies to space (memory) as well as time.

• $O(1)$ space — the algorithm uses a fixed amount of memory regardless of input size (e.g. bubble sort uses only a temp variable)
• $O(n)$ space — memory grows proportionally with input size (e.g. merge sort needs an auxiliary array of size $n$)
• $O(n^2)$ space — adjacency matrix for a graph with $n$ vertices

Time and space complexity may trade off against each other. An algorithm with better time complexity often requires more memory (e.g. merge sort vs bubble sort).

1. Retaining constant factors in Big-O

$O(3n^2)$ is written as $O(n^2)$. Big-O ignores constant multipliers. Writing $O(3n^2)$ is not wrong in the strictest sense, but is non-standard and would not earn full marks in an exam answer asking for Big-O class.

2. Giving best-case complexity when worst-case is asked

Exam questions typically ask about worst-case complexity. Bubble sort worst-case is $O(n^2)$, not $O(n)$ (which is only the optimised best case).

3. Confusing $O(n\log n)$ with $O(n^2)$

Merge sort is $O(n\log n)$; bubble sort is $O(n^2)$. Since $\log n\ll n$, these are very different classes for large $n$.

4. Forgetting to take the dominant term

$O(n^2+n)$ simplifies to $O(n^2)$. Only the fastest-growing term matters asymptotically.