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 / ii

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.