Cambridge 9618 · International A Level Computer Science · ~18 min read
Notes
Video
Slides
Quiz
Worksheet
What is Algorithm Complexity?
Algorithm complexity measures how the time or space an algorithm requires scales as the input size (n) grows. Rather than measuring exact seconds (which depend on hardware), we describe the growth rate using Big O notation.
Key insight: We only care about the dominant term as n becomes very large. Constants and lower-order terms are ignored because they become irrelevant for large n.
3n + 5 → O(n) — the constant 3 and +5 are ignored
n² + 100n + 50 → O(n²) — n² dominates as n grows
5 log n + 3 → O(log n) — the constant 5 is dropped
Common Time Complexities
⚡
O(1)
Constant time. Execution time does not depend on input size. Examples: accessing an array element by index (Arr[i] — always one operation regardless of n); hash table lookup (average); push/pop on a stack; enqueue/dequeue on a queue.
📉
O(log n)
Logarithmic time. Each step halves (or otherwise divides) the problem. Very efficient for large n. Examples: binary search (halves search space each step); BST search/insert on a balanced tree; raising to a power using repeated squaring.
📏
O(n)
Linear time. Time grows directly with input size. One step per element. Examples: linear search; reading all elements of an array; traversing a linked list; BFS/DFS on a graph (O(V+E), considered linear in the size of the input).
🔀
O(n log n)
Linearithmic time. Slightly worse than linear — common in efficient sorting. Examples: merge sort (ALWAYS O(n log n)); quicksort (AVERAGE O(n log n)); heapsort. This is generally the best possible for comparison-based sorting.
📈
O(n²)
Quadratic time. Common with nested loops where both iterate n times. Acceptable for small n (<1000) but impractical for large datasets. Examples: bubble sort, insertion sort, selection sort; checking all pairs in an array; matrix multiplication (naïve O(n³)).
💥
O(2ⁿ)
Exponential time. Doubles with each additional input element. Only feasible for very small n (<30). Examples: generating all subsets of a set; naive recursive Fibonacci (O(2ⁿ)); solving the Towers of Hanoi; brute-force searching all possibilities (NP-complete problems).
Growth Rate Table
Complexity
n = 10
n = 100
n = 1,000
n = 1,000,000
O(1)
1
1
1
1
O(log n)
3
7
10
20
O(n)
10
100
1,000
1,000,000
O(n log n)
33
664
9,966
~20M
O(n²)
100
10,000
1,000,000
10¹²
O(2ⁿ)
1,024
10³⁰
10³⁰⁰
≈∞
Determining Complexity from Code
Simple counting rules:
Single loop iterating n times → O(n)
Two nested loops each iterating n times → O(n²)
Loop that halves on each iteration → O(log n)
Sequence of n-loop then another n-loop (not nested) → O(n) + O(n) = O(n)
Recursive halving with O(n) work per level → O(n log n)
// O(1) — no loops, fixed operations x ← Arr[5] // always 1 step
// O(n) — single loop FORi ← 1TOn Process(Arr[i]) // n iterations NEXTi
Big O is often used for worst case, but best and average cases also matter:
Best Case
Ω (Omega)
Most favourable input. E.g. linear search: target is first element → O(1). Bubble sort on already-sorted: O(n).
Average Case
Θ (Theta)
Expected performance on typical input. E.g. linear search: O(n/2) = O(n). Quick sort: O(n log n).
Worst Case
O (Big O)
Most unfavourable input. E.g. linear search: target not present → O(n). Quick sort worst: O(n²).
Summary: Algorithm Complexities You Need to Know
Algorithm
Best
Average
Worst
Space
Linear Search
O(1)
O(n)
O(n)
O(1)
Binary Search
O(1)
O(log n)
O(log n)
O(1)
Bubble Sort
O(n)*
O(n²)
O(n²)
O(1)
Insertion Sort
O(n)*
O(n²)
O(n²)
O(1)
Merge Sort
O(n log n)
O(n log n)
O(n log n)
O(n)
Quick Sort
O(n log n)
O(n log n)
O(n²)
O(log n)
BST Search
O(1)
O(log n)
O(n)**
—
Hash Table Lookup
O(1)
O(1)
O(n)***
O(n)
BFS / DFS
O(V + E)
O(V)
* Bubble/insertion sort O(n) best case requires early termination flag. ** BST worst case O(n) for degenerate (linear chain) tree. *** Hash table O(n) worst case with many collisions (rare with good hash function).
Space Complexity
Space complexity measures how much extra memory an algorithm requires (auxiliary space — not counting the input itself).
O(n²): adjacency matrix for a graph with n vertices
Cambridge 9618 exam tip: Know how to IDENTIFY the Big O complexity of a given algorithm or code snippet. Key rules: one loop = O(n); nested loops = O(n²); repeated halving = O(log n). When asked to "describe" complexity, always state what n represents (e.g. "O(n) where n is the number of elements"). When comparing algorithms, state BOTH time AND space complexity. Know the difference between worst-case (Big O), average-case (Theta), and best-case (Omega) — Cambridge questions may ask for all three. Remember: "asymptotic" means as n approaches infinity — constants don't matter.
⚠️ Common Mistakes
Keeping constants in Big O — O(3n) = O(n), O(n²/2) = O(n²). Big O drops constants because they become insignificant compared to the growth rate for large n. Write O(n) not O(2n), O(n²) not O(n²+n).
Confusing best/average/worst case — "O(n) average" for linear search does NOT mean it's always fast. The WORST case is still O(n). Quick sort AVERAGE is O(n log n) but WORST is O(n²) — both are true at the same time.
Thinking O(n log n) is "between O(n) and O(n²)" in terms of category — that's correct, but remember n log n grows much closer to n than to n². For n=1000: O(n)=1,000, O(n log n)≈10,000, O(n²)=1,000,000.
Forgetting space complexity — every algorithm has a time AND space complexity. Merge sort's O(n) space overhead (the merge buffer) is a significant disadvantage in memory-constrained environments. Quick sort's O(log n) stack space is often forgotten.
Confusing O(log n) base — in computing, log n in Big O always means log₂n (binary logarithm) because most algorithms that are O(log n) work by halving. But for Big O purposes, the base doesn't matter (different bases differ only by a constant factor, which Big O ignores anyway).
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 4.4.3 Algorithm Complexity
8 questions · Cambridge 9618 standard
Q1Determine the time complexity of each code fragment and justify your answer: (a) A single FOR loop from 1 to n. (b) Two nested FOR loops both from 1 to n. (c) A WHILE loop where a variable doubles each iteration until it exceeds n.[6]
✅ Mark scheme
(a) O(n) [1]: the loop body executes exactly n times — once per value of the loop variable from 1 to n. As n doubles, the work doubles → linear growth [1]; (b) O(n²) [1]: outer loop runs n times, inner loop runs n times for each outer iteration → n × n = n² total iterations. As n doubles, work quadruples → quadratic growth [1]; (c) O(log n) [1]: if the variable doubles each iteration (×2 per step), after k iterations the variable equals 2^k. It stops when 2^k > n → k = log₂n iterations. The number of steps grows logarithmically with n. As n doubles, only ONE more iteration is needed → O(log n) [1]. Total 6 marks — 1 complexity + 1 justification per part.
Q2Simplify the following expressions to Big O notation: (a) 5n + 12. (b) 3n² + 100n + 50. (c) 2n log n + n. (d) n + log n.[4]
✅ Mark scheme
(a) O(n) [1]: drop constant coefficient (5) and constant term (+12) — only the dominant term and its growth rate matter, not its exact coefficient; (b) O(n²) [1]: n² dominates 100n for large n — when n=1000: n²=1,000,000 >> 100n=100,000; drop lower-order term 100n and constant 50 and coefficient 3; (c) O(n log n) [1]: n log n dominates n — when n=1000: n log n ≈ 10,000 >> n=1,000; drop the n term and constant coefficient 2; (d) O(n) [1]: n dominates log n — when n=1000: n=1000 >> log n≈10; n grows much faster than log n so log n is negligible. Full marks only for correct simplification to standard Big O notation.
Q3State the best, average, and worst-case time complexity of quick sort. For each case, describe the input scenario that produces it.[6]
✅ Mark scheme
Best case: O(n log n) [1]. Occurs when the pivot consistently divides the array into two equal halves — producing a balanced recursion tree of height log n with O(n) work at each level [1]; Average case: O(n log n) [1]. Occurs for random pivot selection on random input — the expected depth of recursion is O(log n) because randomly chosen pivots tend to produce reasonably balanced partitions on average [1]; Worst case: O(n²) [1]. Occurs when the pivot is always the minimum or maximum element of the remaining partition — this creates maximally unbalanced partitions (sizes 0 and n-1); the recursion tree has n levels (not log n) with O(n) work at each level → O(n²) total. This happens when the array is already sorted (ascending or descending) and the pivot is always chosen as the first or last element [1].
Q4Algorithm A runs in O(n log n) and algorithm B runs in O(n²). For what values of n might B actually be faster in practice? Explain your reasoning.[3]
✅ Mark scheme
For very small n [1], B might be faster: Big O ignores constants, but in practice each algorithm has a constant factor in front of the dominant term; if B has a much smaller constant than A, then for small n, B's constant × n² might be less than A's constant × n log n [1]; example: insertion sort (O(n²)) is often faster than merge sort (O(n log n)) for n < 10-20 elements because insertion sort has a very small constant factor and low overhead — no recursive calls, no merge buffer allocation; merge sort's larger constant overhead dominates at small n [1]. The crossover point where A becomes faster depends on the specific implementation and hardware — for large n, O(n log n) ALWAYS wins because asymptotically n log n grows slower than n². Accept any reasonable threshold (e.g. n < 10 or n < 50) with justification.
Q5Explain the difference between TIME complexity and SPACE complexity. Give one example of an algorithm where there is a trade-off between the two.[4]
✅ Mark scheme
Time complexity: measures how the NUMBER OF OPERATIONS (or execution time) scales with input size n [1]; Space complexity: measures how much EXTRA MEMORY (auxiliary space) the algorithm requires, beyond the input itself, as n grows [1]; Example of trade-off — Merge sort vs Quick sort [1]: merge sort uses O(n) extra space (temporary arrays for merging) but achieves guaranteed O(n log n) time in ALL cases; quick sort uses only O(log n) extra space (recursion stack) — much more space-efficient — but has O(n²) worst case. To get better time guarantees (merge sort), you must pay more space. Another example: hash table — O(n) space for the table gives O(1) average lookup; an unsorted array uses O(n) space but O(n) lookup. Trading space (hash table overhead) for time (O(1) vs O(n)) [1]. Accept any valid example with explanation.
Q6A binary search function is called on an array of 1,024 elements. How many comparisons does it take at most to find (or determine absence of) any element? Show your working using Big O.[3]
✅ Mark scheme
Binary search is O(log₂ n) comparisons worst case [1]; n = 1024 = 2¹⁰ [1]; therefore maximum comparisons = log₂(1024) = 10 comparisons [1]. Each comparison halves the remaining search space: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. At most 10 comparisons to either find the element or determine it is not in the array. Compare this with linear search worst case: 1024 comparisons. Binary search is 100× more efficient here. Award all 3 marks for correct formula + correct calculation of log₂1024=10.
Q7Determine the time complexity (Big O notation) of the following pseudocode and justify your answer: FOR i ← 1 TO n / FOR j ← 1 TO n / FOR k ← 1 TO 100 / OUTPUT i, j, k / NEXT k / NEXT j / NEXT i[4]
✅ Mark scheme
The outer loop runs n times [1]; the middle loop runs n times for each iteration of the outer loop, giving n² total [1]; the inner loop runs 100 times — this is a constant, not dependent on n [1]; constants are dropped in Big O notation, so overall complexity is O(n²) [1].
Q8Algorithm A has complexity O(n log n) and Algorithm B has complexity O(n²). For small values of n (e.g. n = 5), B may execute fewer operations. Explain the concept of a crossover point and state why, for large n, A will always outperform B.[4]
✅ Mark scheme
The crossover point is the value of n at which algorithm A becomes faster than algorithm B [1]; for n below the crossover, B's lower constant factors may make it faster in practice despite higher theoretical complexity [1]; as n grows, n² grows much faster than n log n because log n grows very slowly (e.g. log₂(1,000,000) ≈ 20 while n = 1,000,000) [1]; beyond the crossover point, the difference in growth rates dominates and A always executes fewer operations for sufficiently large n [1].
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 8
Click to reveal definition
🎉
All cards reviewed!
Notation
Meaning
🎯
Mini Test — 4.4.3 Complexity
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1Two nested loops, each iterating n times, gives a time complexity of:
Q2Which sorting algorithm always runs in O(n log n) regardless of input order?
Q3What is the Big O simplification of 3n² + 50n + 100?
Q4An algorithm's variable doubles each iteration until it exceeds n. This gives:
Q5Which algorithm uses O(n) EXTRA SPACE due to its merge buffer?
Section B — Short Answer [5 marks]
Q6State the worst-case time complexity of each: (a) linear search (b) binary search (c) bubble sort (d) merge sort (e) quick sort.
Mark scheme(a) O(n) [1 for all 5 correct]; (b) O(log n); (c) O(n²); (d) O(n log n); (e) O(n²). Note: merge sort is unique in having best=average=worst = O(n log n). Quick sort worst = O(n²) due to degenerate pivot choice. Award marks: 2 correct=0, 3 correct=1, 4 correct=2 (partial), all 5 correct=full marks at 1 mark for the set.
Q7Explain what O(n²) means in plain English, and give one example of an algorithm that runs in O(n²).
Mark schemeO(n²) means the number of operations grows proportionally to the SQUARE of the input size n [1]; if n doubles, the work quadruples; if n triples, the work grows ninefold [1]; example: bubble sort, insertion sort, or selection sort — each requires approximately n²/2 comparisons in the average/worst case due to the nested loop structure (outer loop n times, inner loop up to n times) [1]. Concrete numbers: for n=100 → ~5,000 comparisons; for n=1,000 → ~500,000 comparisons; for n=10,000 → ~50,000,000 comparisons — grows rapidly.
Q8Explain why Big O notation ignores constant factors. Give an example.
Mark schemeBig O describes the GROWTH RATE as n approaches infinity — it characterises how rapidly an algorithm's resource use grows, not the exact value for a specific n [1]; constant factors depend on implementation details (hardware speed, language, compiler optimisations) rather than the algorithm's inherent scalability — they are machine-dependent and irrelevant to theoretical analysis [1]; example: O(3n) and O(n) both describe algorithms where the work doubles when n doubles — the "3" is a fixed implementation detail, not a property of the algorithm's scaling. On one machine an O(5n) algorithm may run faster than an O(2n) algorithm on a slower machine — constants are absorbed into practical differences that don't affect the fundamental growth rate [1].
Q9Give one advantage of a hash table (average O(1) lookup) over a binary search tree (O(log n) lookup), and one disadvantage.
Mark schemeAdvantage: hash table provides O(1) AVERAGE lookup — much faster than BST's O(log n) for large n; for 1,000,000 elements: hash table ≈ 1 comparison (average), BST ≈ 20 comparisons. This is a significant practical advantage for frequent lookups [1]; Disadvantage: hash table does NOT maintain sorted order — you cannot traverse a hash table in sorted key order without sorting; BST gives sorted order via in-order traversal (O(n)) [1]. Also accept: hash table worst case is O(n) with many collisions; BST gives O(log n) worst case (balanced tree) which is guaranteed. Hash table requires a good hash function; BST works with any comparable keys [accept as alternative disadvantage].
Q10An algorithm is O(2ⁿ). It takes 1 second for n=20. Approximately how long would it take for n=30? Show your reasoning.
Mark schemeO(2ⁿ) means time is proportional to 2ⁿ [1]; For n=20: time ∝ 2²⁰ = 1,048,576. For n=30: time ∝ 2³⁰ = 1,073,741,824 [1]; ratio = 2³⁰ / 2²⁰ = 2¹⁰ = 1024. So it takes approximately 1,024 times longer [1]; If n=20 takes 1 second, then n=30 takes approximately 1,024 seconds ≈ 17 minutes. This illustrates why exponential algorithms are only feasible for very small inputs. Going from n=20 to n=30 (a 50% increase in input size) causes a 1024× (100,000%) increase in runtime — exponential growth is catastrophic. Award all 3 marks for correct ratio calculation with clear working.