A2 · Practice questions · Comparing algorithms: Big O notation

Growth, not seconds.

Six original Cambridge-style questions on comparing algorithms and Big O notation.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.

Keep these straight

Dominant term only.

Criteria: time taken (operations as n grows) and memory used (extra storage).
Simplify: keep the dominant term, drop constants: 4n² + 9n is O(n²).
Order: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
Predict: scale n by k and the time scales by k for O(n), k² for O(n²).

Explain

[3 marks]

Explain what is meant by Big O notation and why it is used to compare algorithms.

It describes the order of growth of an algorithm's time (or space) requirement as the number of data items n increases. ✓
It usually describes the worst case and ignores constants and lower-order terms. ✓
It allows algorithms to be compared independently of hardware and programming language / shows how well each scales to large data. ✓

Analysis

[4 marks]

State the time complexity of each algorithm in Big O notation: (a) binary search (b) bubble sort (c) linear search (d) popping an item from a stack.

(a) O(log n). ✓
(b) O(n²). ✓
(c) O(n). ✓
(d) O(1). ✓

Calculate

[3 marks]

An O(n) algorithm and an O(n²) algorithm each take 0.4 seconds to process 500 records. Estimate how long each takes for 2500 records. Show your working.

2500 / 500 = 5 times the data. ✓
O(n): 0.4 × 5 = 2 seconds. ✓
O(n²): 0.4 × 5² = 0.4 × 25 = 10 seconds. ✓

Trace

[3 marks]

State how many times Total ← Total + i * j is executed when n = 8, and give the time complexity:

FOR i ← 1 TO n
    FOR j ← 1 TO 4
        Total ← Total + i * j
    NEXT j
NEXT i

The inner loop always runs 4 times, whatever n is. ✓
8 × 4 = 32 times. ✓
4n grows linearly with n, so O(n) (the inner loop is not over the data). ✓

Explain

[4 marks]

A program stores 100 000 product codes. Compare keeping them in an unsorted array and searching with a linear search, with keeping them in a sorted array and searching with a binary search. Refer to time and space complexity.

Linear search is O(n): up to 100 000 comparisons; binary search is O(log n): at most 17 comparisons. ✓
Both searches need only O(1) extra memory (a few variables). ✓
The sorted array must be kept in order, so inserting a new code costs time (items must be shifted, O(n)). ✓
If searches are much more frequent than inserts, the sorted array with binary search is better. ✓

Analysis

[3 marks]

A recursive function calls itself n times before reaching its base case, and each call does a fixed amount of work. State its time complexity and its space complexity, and explain the space complexity.

Time: O(n). ✓
Space: O(n). ✓
Each call that has not yet returned keeps a stack frame (return address, parameters, local variables) on the call stack, so up to n frames are held at once. ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.