Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 5 / d

Let $f_j$ be the determinant of the leading $j\times j$ principal submatrix. Expansion along the last row gives an $a_j{f}_{j-1}$ term and a $c_{j-1}$ term with negative cofactor sign. In the latter minor, the final column has only $b_{j-1}$ nonzero, and deleting that row and column leaves the leading $(j-2)\times (j-2)$ principal submatrix. Thus the tridiagonal determinant recurrence isHere $f_0=1$ is the empty determinant convention, needed to include $f_2=a_1{a}_2-b_1{c}_1$. The derivation uses cofactor expansion, so the recurrence relation remains valid when coefficients or intermediate determinants vanish; it never divides by a pivot element.

Evaluate the recurrence relation successively, retaining only the preceding two values. Each of the $n-1$ updates uses three multiplications and one subtraction. Hence $4(n-1)=O(n)$ arithmetic operations and $O(1)$ auxiliary storage suffice, excluding the stored input. Naively branching into two recursive calls would repeat work; the sequential computation is essential. This is an arithmetic-operation bound, not a bit-complexity bound for arbitrarily large exact integers.