CAIE 9618 · Paper 4 · Topic 4.4.3

Algorithm
Complexity

Big-O Notation · Time Complexity · Space Complexity · Best/Worst/Average Cases

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 scale as the input size n grows. It expresses the worst-case upper bound, ignoring constants and lower-order terms (e.g. 3n² + 2n → O(n²)).

Big-O	Name	Example	n=10	n=100	n=1000
O(1)	Constant	Hash table lookup, array access	1	1	1
O(log n)	Logarithmic	Binary search, BST search	3	7	10
O(n)	Linear	Linear search, traversal	10	100	1000
O(n log n)	Linearithmic	Merge sort, quick sort (avg)	33	664	10,000
O(n²)	Quadratic	Bubble/insertion sort, nested loops	100	10,000	1,000,000
O(2ⁿ)	Exponential	Fibonacci (naive), subset generation	1,024	10³⁰ — impractical
O(n!)	Factorial	Travelling salesman (brute force)	3,628,800	Impossible

ORDER OF GROWTH (fastest → slowest)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Identifying Complexity

How to Determine Big-O

RULES

Single loop over n items → O(n)

Two nested loops over n → O(n²)

Halving the problem each step → O(log n)

n × halving (e.g. merge sort) → O(n log n)

Recursive call on all subsets → O(2ⁿ)

Drop constants and lower-order terms: O(3n² + 2n + 5) = O(n²)

BEST vs WORST vs AVERAGE CASE

Best case — most favourable input (e.g. target at index 0 for linear search) → O(1)

Worst case — least favourable input (e.g. target not in list) → O(n). Big-O is typically worst case.

Average case — expected performance on typical input → O(n/2) = O(n)

SPACE COMPLEXITY

How much extra memory the algorithm uses as n grows. Merge sort: O(n) — needs temp array. Quick sort: O(log n) stack. Bubble/insertion: O(1) — in-place. Hash table: O(n) storage.

Exam Practice

Cambridge-style questions

Question 1

State the time complexity (Big-O) of each of the following: (a) accessing an element in an array using its index; (b) searching an unsorted list of n elements for a target value; (c) a standard bubble sort on n elements; (d) searching a balanced binary search tree of n nodes. [4]

1

(a) O(1) — array indexing is direct memory access; time does not depend on n.

1

(b) O(n) — linear search; in the worst case all n elements must be checked.

1

(c) O(n²) — bubble sort uses nested passes; for n elements approximately n² comparisons in the worst case.

1

(d) O(log n) — balanced BST halves the search space at each comparison; maximum depth = log₂ n.

Common Mistakes

Don't lose easy marks

1

Writing O(n/2) instead of O(n) — Big-O ignores constant factors. O(n/2), O(2n), O(100n) are all O(n). Only the dominant growth term matters, without coefficients or constants.

2

Confusing time and space complexity — Big-O can refer to either. If a question asks about memory usage, it wants space complexity. If it asks about execution time, it wants time complexity. Read the question carefully — bubble sort is O(1) space but O(n²) time.

3

Saying O(n log n) is worse than O(n²) — it is NOT. O(n log n) grows slower than O(n²). Always remember the order: O(n log n) is between O(n) and O(n²). For large n, merge sort O(n log n) is dramatically faster than bubble sort O(n²).

Topic Summary — 4.4.3

What You Need to Know

BIG-O ESSENTIALS

O(1) constant, O(log n) binary search/BST, O(n) linear, O(n log n) merge/quick sort, O(n²) bubble/insertion/nested loops, O(2ⁿ) exponential, O(n!) factorial. Drop constants.

CASES

Best case: most favourable input. Worst case: least favourable (Big-O default). Average case: typical input. Know all three for bubble sort (O(n) best, O(n²) worst) and binary search (O(1) best, O(log n) worst).

SPACE COMPLEXITY

Measures extra memory used. O(1) = in-place (bubble, insertion, quick). O(n) = extra array (merge sort). O(log n) = recursion stack (quick sort).

CSZone

Next Video

4.5.1

SQL & Relational Databases

SELECT · JOIN · WHERE · GROUP BY · Relational Model

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools