 Solution

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.