= 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 \b[$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>.
Back to article page
