SLIDE 1
CSZone.co.uk
Click to advance · Arrow keys also work
CAIE 9618 · Paper 2 · Topic 2.4.5

Big-O
Notation

Time Complexity · O(1) · O(n) · O(log n) · O(n²) · Comparing Algorithms

CSZone Cambridge International AS & A Level Computer Science 9618
Big-O Notation

Measuring Algorithm Efficiency

Big-O notation describes how an algorithm's time (or space) requirements grow as the input size n increases. It focuses on the dominant term and ignores constants — we care about the growth rate, not the exact number of operations.
WHY BIG-O?
Allows fair comparison of algorithms regardless of hardware speed. A slow computer running O(n log n) sort will eventually beat a fast computer running O(n²) sort as n grows large enough.
KEY RULE
Drop constants and lower-order terms. 3n² + 5n + 2 is O(n²) — the n² term dominates as n grows large. Big-O gives the worst-case upper bound.
O(1) and O(n)

Constant and Linear Time

O(1) — CONSTANT TIME
Time does not depend on input size. Always the same number of operations. The most efficient complexity.
Examples: array index access arr[i], stack Push/Pop, hash table lookup (average)
// O(1): always 1 step
OUTPUT arr[5]
O(n) — LINEAR TIME
Time grows proportionally with n. Double the input → double the time. Very common in algorithms that visit every element once.
Examples: linear search, traversing a linked list, reading n items from a file
// O(n): n iterations
FOR i <- 1 TO n
OUTPUT arr[i]
NEXT i
O(log n) and O(n²)

Logarithmic and Quadratic Time

O(log n) — LOGARITHMIC TIME
Problem size halved each step. Doubling n only adds 1 extra step. Very efficient for large inputs.
Examples: binary search, BST search (balanced), binary tree operations
// O(log n): halve each step
// Binary search — n=1024 needs only ~10 steps
O(n²) — QUADRATIC TIME
Time grows with the square of n. Double n → 4× longer. Acceptable for small n, but very slow for large inputs.
Examples: bubble sort, insertion sort, selection sort, nested loops comparing all pairs
// O(n²): nested loops
FOR i <- 1 TO n
FOR j <- 1 TO n
// n × n = n² operations
Comparison

Big-O at a Glance

NOTATION NAME n=100 STEPS (approx) EXAMPLE
O(1) Constant 1 Array index access
O(log n) Logarithmic ~7 Binary search
O(n) Linear 100 Linear search
O(n log n) Linearithmic ~700 Merge sort
O(n²) Quadratic 10,000 Bubble sort
Best → worst efficiency: O(1) < O(log n) < O(n) < O(n log n) < O(n²)
Identifying Big-O

From Code to Complexity

SINGLE LOOP → O(n)
FOR i <- 1 TO n
// one statement
NEXT i
NESTED LOOPS → O(n²)
FOR i <- 1 TO n
FOR j <- 1 TO n
// statement
NEXT j
NEXT i
HALVING EACH STEP → O(log n)
// Binary search
low <- 1 ; high <- n
WHILE low <= high
mid <- (low+high) DIV 2
// halve each iteration
ANY FIXED STEPS → O(1)
If the number of operations doesn't change as n grows — it's O(1), regardless of how many fixed steps there are.
Exam Practice

Cambridge-style questions

Question 1
An algorithm searches a sorted list of n items using binary search. State the time complexity in Big-O notation and explain why doubling n from 1024 to 2048 only adds approximately one extra step.
3 marks
Time complexity: O(log n)  1
Binary search halves the search space with each comparison.  1
For n=1024, max steps ≈ 10 (log₂ 1024). For n=2048, max steps ≈ 11 (log₂ 2048). Doubling n only adds one more comparison because log₂(2n) = log₂(n) + 1.  1
Exam Practice

Cambridge-style questions

Question 2
Give the Big-O time complexity of each of the following: (a) Accessing element arr[i] in an array; (b) Bubble sort on a list of n items; (c) Linear search on an unsorted list of n items. [3 marks]
3 marks
(a) O(1) — array access is a direct index lookup, constant time regardless of array size.  1
(b) O(n²) — bubble sort uses nested loops, comparing each pair of adjacent elements up to n times.  1
(c) O(n) — linear search visits each element once in the worst case.  1
Common Mistakes

Don't lose easy marks

1
Including constants in Big-O. The answer is O(n) not O(3n) or O(n+5). Big-O drops all constants and lower-order terms — only the dominant growth term counts.
2
Confusing O(log n) with O(n). Binary search is O(log n) because it halves the problem each step. Linear search is O(n). Always justify your answer by describing how the problem size changes per step.
3
Giving Big-O without justification. Exam questions often ask you to explain your answer. State the complexity AND say why — e.g. "O(n²) because there are two nested loops, each running n times, giving n × n = n² operations."
Topic Summary — 2.4.5

What You Need to Know

BEST COMPLEXITIES
O(1) — constant: fixed operations
O(log n) — logarithmic: halving (binary search)
O(n) — linear: one pass through data
WORST COMPLEXITY (GCSE/A-Level)
O(n²) — quadratic: nested loops (bubble sort)
Acceptable for small n, impractical for large n
KEY RULES
Drop constants: 5n → O(n)
Drop lower terms: n² + n → O(n²)
Single loop → O(n)
Nested loops → O(n²)
Halving each step → O(log n)
Fixed steps → O(1)
CSZone

Section Complete

CAIE 9618 · Paper 2
Algorithm Efficiency
You can now compare algorithms using Big-O notation
Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools