Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 120 / 1 / c / Solution

Part (a)(i), applied to $w=u$ and $g=\overline{u}x$, guarantees an accepted output of length at most $m+N$. Its padded convolution of words has at most $m+N$ columns. Thus the dynamic programming search in part (b) reaches an accepting layer by this bound.

Each layer has at most twice the fixed number of states of $M_x$, and each record has at most $|A|+1$ outgoing choices. These are constants for the fixed automatic structure for a group. Storing a pointer and a symbol takes constant time; copying whole partial output strings at every step would unnecessarily spoil this bound. Reconstruction also takes at most $m+N$ steps. Therefore automatic multiplication has linear time and bounded length increase:For nonempty inputs this is the requested $O(|u|)$ time complexity. The additive $1$ merely includes the constant work on the empty word.