Big O Notation

This lesson covers Big O notation — the standard way to express the efficiency of algorithms in terms of time and space. Understanding algorithmic complexity is essential for the OCR A-Level Computer Science (H446) specification.

---

Why Measure Efficiency?

Two algorithms can solve the same problem but differ dramatically in how long they take or how much memory they use. Measuring efficiency allows us to:

• Compare algorithms objectively.
• Predict how an algorithm will scale as input size grows.
• Choose the best algorithm for a given problem.

---

What is Big O Notation?

Big O notation describes the worst-case (or upper bound) growth rate of an algorithm's resource usage (time or space) as the input size n grows towards infinity.

It focuses on the dominant term and ignores:

• Constants (e.g., 3n becomes O(n))
• Lower-order terms (e.g., n^2 + 5n + 10 becomes O(n^2))

---

Common Time Complexities

Big O	Name	Example	Performance
O(1)	Constant	Array access by index, hash table lookup	Excellent
O(log n)	Logarithmic	Binary search	Very good
O(n)	Linear	Linear search, traversing a list	Good
O(n log n)	Linearithmic	Merge sort, quick sort (average)	Decent
O(n^2)	Quadratic	Bubble sort, insertion sort (worst)	Poor for large n
O(2^n)	Exponential	Recursive Fibonacci (naive), brute-force subset problems	Very poor
O(n!)	Factorial	Brute-force travelling salesman	Extremely poor

---

Visualising Growth Rates

For n = 10, 100, 1000, 10000:

n	O(1)	O(log n)	O(n)	O(n log n)	O(n^2)	O(2^n)
10	1	3	10	33	100	1,024
100	1	7	100	664	10,000	1.27 x 10^30
1,000	1	10	1,000	9,966	1,000,000	Unfathomable
10,000	1	13	10,000	132,877	100,000,000	Unfathomable

This table shows why O(n^2) algorithms become impractical for large n, and O(2^n) algorithms are infeasible for even modest n.

---

Determining Big O

Rules

1. Drop constants: O(3n) = O(n); O(100) = O(1).
2. Drop lower-order terms: O(n^2 + n) = O(n^2); O(n + log n) = O(n).
3. Consider the worst case (unless otherwise stated).
4. Count the dominant operation (comparisons, assignments, etc.).

Examples

Code Pattern	Time Complexity	Explanation
Single operation	O(1)	Does not depend on input size
Single loop (0 to n)	O(n)	Loop runs n times
Nested loops (n x n)	O(n^2)	Inner loop runs n times for each outer iteration
Halving the input each step	O(log n)	Input divided by 2 each iteration
Loop * halving	O(n log n)	e.g., merge sort's merge step across log n levels

Worked Example: Counting Operations

function example(n)
    total = 0                    // O(1)
    for i = 0 to n - 1           // O(n)
        for j = 0 to n - 1       // O(n)
            total = total + 1    // O(1)
        next j
    next i
    return total                 // O(1)
endfunction