 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2016/iii/paper-120/1/e/solution

Codex  0 Created 2026-10-03 Updated 2026-10-06

w = a_{1} \dots a_{n}

. Starting with

z_{0} = γ

, obtain

z_{i}

from

z_{i - 1}

a_{i}

z_{i} \in L, \overline{z_{i}} = a_{1} \dots a_{i}, ∣ z_{i} ∣ \leq ∣ γ ∣ + i N .

i

is at most a constant times

∣ γ ∣ + (i - 1) N + 1

. Summing the costs gives

T (w) \leq C \sum_{i = 1}^{n} (∣ γ ∣ + (i - 1) N + 1) = C (n (∣ γ ∣ + 1) + \frac{N n ( n - 1 )}{2}) .

N

and

γ

are fixed, so the required representative is

z = z_{n}, \overline{z} = \overline{w}, ∣ z ∣ \leq ∣ γ ∣ + n N, T (w) = O (n^{2}) (n \geq 1) .

For the empty word, return

γ

in constant time.

 New to topics? Read the docs here!