Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 41C / b / i / Solution

The first stage isBecause $A_y=I\otimes T$, this consists of $m$ independent tridiagonal systems of dimension $m$. The Thomas algorithm solves each in $O(m)$ operations, for a total of $O(m^2)$.

The second stage,is multiplication by a matrix with only $O(m^2)$ nonzero entries, so it also costs $O(m^2)$. Hence one complete step uses at mostarithmetic operations.