Classification of algorithms, Big-O, halting problem and Turing machines – A-level Computer Science exam questions with mark scheme

1Standard4 marks

(a) State the time complexity of the following algorithm in terms of n. [1]

FOR i ← 1 TO n
  FOR j ← 1 TO n
    OUTPUT i * j
  ENDFOR
ENDFOR

(b) State the time complexity of a binary search on a sorted list of n items. [1]

(c) An algorithm with time complexity O(n²) takes 4 ms for n = 1000. Estimate the time it takes for n = 3000. Show your working. [2]

(a) O(n²)(1)
(b) O(log n)(1)
(c) n is multiplied by 3, so time is multiplied by 3² = 9(1)
(c) 4 × 9 = 36 ms(1)
Answer: (a) O(n^2) (b) O(log n) (c) 36 ms
Examiner tip: For O(n²), multiplying the input size by k multiplies the time by k², not by k.

2Hard6 marks

A Turing machine has the transition table below. Symbols are 0, 1 and _ (blank). The tape is blank on both sides of the input. The head starts on the leftmost symbol of the input in state q0. H is the halting state. Each rule is (new state, symbol written, direction).

State	Read 0	Read 1	Read _
q0	(q0, 0, R)	(q0, 1, R)	(q1, _, L)
q1	(H, 1, R)	(q1, 0, L)	(H, 1, R)

(a) The tape initially holds 1011. Give the tape contents when the machine halts. [1]

(b) State what the machine does to the binary number on the tape. [1]

(c) State the number of transitions the machine makes on the input 1011, including the one that enters H. Show your working. [2]

(d) Explain why a Turing machine is a useful model of computation. [2]

(a) 1100(1)
(b) Adds 1 to the number (increments it)(1)
(c) State q0 makes 5 transitions (4 moves right over the digits and 1 on the blank)(1)
(c) State q1 makes 3 transitions (1→0, 1→0, then 0→1 and halt), giving 8 in total; accept any correct trace showing all 8 transitions with total 8 for both (c) marks; 8 with no working scores 1 mark(1)
(d) It is a simple abstract/formal model (tape, read/write head, states, transition rules) that is independent of any hardware or programming language(1)
(d) Any problem that can be solved by an algorithm can be solved by a Turing machine, so it is used to define/reason about what is and is not computable; accept: a Universal Turing machine can simulate any other Turing machine given its description, which is the basis of the stored-program computer / interpreter(1)
Answer: (a) 1100 (b) Adds 1 (c) 8 (d) A simple, hardware-independent model of anything computable
Examiner tip: Count every transition, including the one on the blank and the final one that writes and halts.

3Standard4 marks

(a) State what is meant by the halting problem. [1]

(b) State the significance of the halting problem for computer scientists. [1]

(a) Determining, for any given program and input, whether the program will eventually halt or run forever(1)
(b) It shows that some problems cannot be solved by a computer / are non-computable (it has been proved that no general algorithm can solve the halting problem); accept: there are problems that no algorithm can solve; NE: 'some programs never stop'(1)
(c) Intractable: an algorithm exists, but there is no polynomial-time (or better) solution, so it takes an unreasonable amount of time for all but small inputs; accept e.g. exponential time(1)
(c) Unsolvable/non-computable: no algorithm can exist that solves every case, however much time or memory is available(1)
Answer: (a) Deciding whether any program halts on a given input (b) Proves some problems cannot be computed (c) Intractable = solvable but impractically slow; unsolvable = no algorithm exists
Examiner tip: Contrast the two ideas clearly: intractable is about time, unsolvable is about impossibility.

Stuck on this topic?

Book a free 30-minute session on WhatsApp and we'll find exactly which step is costing you the marks. Or build a timed paper on it.

Free 30-minute session