Cambridge 9618 · International A Level Computer Science · ~15 min read
Notes
Video
Slides
Quiz
Worksheet
What is Big-O Notation?
Big-O notation describes how an algorithm's time requirements (or memory usage) grow as the input size n increases. It focuses on the dominant term and worst-case behaviour — ignoring constants and lower-order terms because for large n they become irrelevant.
Big-O answers the question: "If I double the input size, how much longer does this algorithm take?"
Key Terms
n — the size of the input (e.g. number of elements in an array)
Time complexity — how the number of operations grows with n
Space complexity — how the memory usage grows with n
Worst case — the maximum number of operations for any input of size n
Best case — the minimum number of operations (e.g. the item is found first)
Average case — typical performance averaged over all possible inputs
The Six Common Complexities
O(1)
Constant
Performance does not change with n. Always the same number of operations regardless of input size.
*Bubble sort O(n) best case requires the early exit (swapped flag) optimisation.
How to Identify Big-O from Code
Single operation, no loop: O(1)
One loop over n items: O(n)
Two nested loops over n items: O(n²)
Problem halved each step: O(log n) — e.g. binary search
Loop over n + halving: O(n log n) — e.g. merge sort
Recursive with two calls on n-1 and n-2: O(2ⁿ) — e.g. Fibonacci
Cambridge exam — state the complexity: Always express complexity in standard form (e.g. "O(n²)", not "n squared" or "quadratic"). For bubble sort, specify whether you mean worst or best case. If asked "which algorithm is more efficient?", always justify your answer by comparing complexities.
⚠️ Common Mistakes
Saying bubble sort is always O(n) — it's O(n) only in the best case with early exit; worst/average is O(n²)
Confusing O(log n) with O(n log n) — binary search is O(log n); merge sort is O(n log n)
Saying merge sort has O(n²) — it's always O(n log n) regardless of input order
Forgetting space complexity — merge sort is O(n) space; bubble/insertion sort are O(1) in-place
Writing O(n) + O(n) = O(2n) — Big-O ignores constants, so O(2n) simplifies to O(n)
Confusing best case and worst case — linear search: best O(1) (found first), worst O(n) (not found)
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 2.4.5 Big-O Notation
8 questions · Cambridge 9618 standard
Q1State what Big-O notation measures and explain why constants are ignored in Big-O analysis.[3]
✅ Mark scheme
Big-O measures how the time (or space) requirements of an algorithm grow as the input size n increases [1]; it describes the worst-case growth rate [1]; constants are ignored because for large n, constants become insignificant compared to the dominant growth term — e.g. 100n is still O(n) because as n grows, the constant 100 has negligible effect relative to n [1].
Q2For each algorithm, state its worst-case time complexity: (a) Linear search, (b) Binary search, (c) Bubble sort, (d) Merge sort.[4]
Q3An algorithm contains two nested FOR loops, each running from 1 to n. State the time complexity and justify your answer.[2]
✅ Mark scheme
O(n²) [1]; the inner loop runs n times for each of the n iterations of the outer loop, giving n×n = n² operations total [1].
Q4A dataset has 1,000,000 records. Compare the approximate number of operations for: (a) linear search, (b) binary search to find a specific record. Why is binary search preferred?[3]
✅ Mark scheme
(a) Linear search worst case: O(n) → up to 1,000,000 comparisons [1]; (b) Binary search worst case: O(log₂ n) → log₂(1,000,000) ≈ 20 comparisons [1]; binary search is far more efficient for large sorted datasets — 20 comparisons vs 1,000,000 comparisons [1].
Q5Order these complexities from most efficient to least efficient: O(n²), O(1), O(n log n), O(log n), O(n), O(2ⁿ).[2]
✅ Mark scheme
O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) [2 marks — 1 mark if mostly correct with no more than one error].
Q6Explain why merge sort (O(n log n)) is preferred over bubble sort (O(n²)) for sorting 100,000 records, even though merge sort uses more memory.[3]
✅ Mark scheme
For n=100,000: bubble sort ≈ 10¹⁰ operations; merge sort ≈ 100,000 × 17 ≈ 1.7 million operations [1]; the O(n log n) vs O(n²) difference is enormous at large n — merge sort is orders of magnitude faster [1]; the extra O(n) memory for merge sort's temporary arrays is a reasonable trade-off for the massive speed improvement when n is large [1].
Q7Write pseudocode for a procedure that opens a file "log.txt", attempts to read a line, and handles two possible errors: (1) the file does not exist, and (2) the file is empty. Use TRY-EXCEPT-FINALLY structure and explain the role of FINALLY.[5]
Q8Explain the difference between a syntax error, a runtime error, and a logic error. For each type, give one example that could occur in a file-handling program and explain how a programmer would detect and fix it.[6]
✅ Mark scheme
Syntax: code that violates language rules, caught at compile time — 1 mark; e.g. OPNFILE instead of OPENFILE — detected by compiler/interpreter — 1 mark; Runtime: occurs during execution, e.g. attempting to read a file that does not exist — 1 mark; detected at run time, handled with TRY-EXCEPT — 1 mark; Logic: program runs but produces wrong output, e.g. reading from wrong file name — 1 mark; detected by testing with known data and comparing output — 1 mark.
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 7
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 2.4.5 Big-O Notation
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1What is the time complexity of accessing a single element from an array by its index?
Q2Which complexity represents binary search?
Q3An algorithm has O(n²) complexity. If n doubles from 100 to 200, operations increase by approximately:
Q4Which sorting algorithm has O(n log n) worst-case time complexity?
Q5What does 'worst case' mean in the context of Big-O?
Section B — Short Answer [5 marks]
Q6State the Big-O notation for each: (a) linear search worst case, (b) binary search worst case, (c) bubble sort best case (with early exit), (d) merge sort worst case.
Q7Explain why O(n²) algorithms become impractical for large datasets.
Mark schemeFor O(n²), operations grow as the square of n [1]; for n=1,000,000 this is 10¹² operations — at 10⁹ operations per second this would take over 1000 seconds [1]; small increases in n cause enormous increases in operation count [1].
Q8A programmer says 3n² + 5n + 100 is O(n²). Are they correct? Explain why Big-O ignores the 5n and 100 terms.
Mark schemeYes, correct [1]; as n grows large, the n² term dominates — for n=1000: n²=10⁶, 5n=5000, 100=100; the smaller terms become negligible [1]; Big-O describes growth rate, so only the dominant term matters; constants and lower-order terms are ignored [1].
Q9Binary search has O(log n) complexity. Approximately how many comparisons are needed to search 1,000,000 sorted records?
Mark schemelog₂(1,000,000) ≈ 20 comparisons [1]; each comparison halves the remaining search space — after 20 halvings, only 1 record remains [1].
Q10State whether each algorithm is in-place (O(1) space) or requires additional memory: (a) bubble sort, (b) merge sort, (c) binary search.
Mark scheme(a) Bubble sort: in-place O(1) extra space — swaps are done within the array [1]; (b) Merge sort: O(n) extra space — needs temporary arrays for the merge step [1]; (c) Binary search: O(1) extra space — only needs a few pointer variables (Low, High, Mid) [1].