سوال ۶۶ کنکور ارشد علوم کامپیوتر ۱۳۹۷

Goal. Compute a single Fibonacci number $f_m$ with the index $m = n^2$, as fast as possible (counting arithmetic operations as unit-cost, which is the usual convention in these exam questions).

Naive bounds (rejected).

• Iterating the recurrence $f_i = f_{i-1} + f_{i-2}$ up to index $m$ costs $\Theta(m)$ additions. With $m = n^2$ that is $\Theta(n^2)$ — option 2, but not the best time.
• The exponential recursive definition is far worse, so it is irrelevant here.

Best method: fast matrix exponentiation / fast doubling. The Fibonacci map is linear:

$\begin{pmatrix} f_{m+1} \\ f_{m} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{m} \begin{pmatrix} f_{1} \\ f_{0} \end{pmatrix}.$

So $f_m$ is read off from $A^{m}$ where $A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. A $2\times 2$ power $A^{m}$ is computed by repeated squaring (exponentiation by squaring) in $\Theta(\log m)$ matrix multiplications, each multiplication being $O(1)$ for a fixed $2\times 2$ matrix.

Substitute the index $m = n^2$:

$\Theta(\log m) = \Theta\!\left(\log\left(n^{2}\right)\right) = \Theta(2\log n) = \Theta(\log n).$

The factor of $2$ from squaring the index is absorbed by the asymptotic notation. Hence the best time is $O(\log n)$ — option 3.

Exam trick: $\log(n^2) = 2\log n = \Theta(\log n)$, so squaring the index does not change the order of the fast-doubling cost. The trap answers are $O(n^2)$ (naive iteration to index $n^2$) and $O(n)$ (mis-simplifying $\log(n^2)$ to $n$).