But how many matrix multiplications does it take to compute Xn$?$

$($b$)$ Show that O$($log n$)$ matrix multiplications suffice for computing Xn$.($Hint: Think about

computing X$8$

$.)$

Thus the number of arithmetic operations needed by our matrix$-$based algorithm, call it fib$3,$ is

just O$($log n$),$ as compared to O$($n$)$ for fib$2.$ Have we broken another exponential barrier?

The catch is that our new algorithm involves multiplication, not just addition; and multiplications of large numbers are slower than additions. We have already seen that, when the complexity of arithmetic operations is taken into account, the running time of fib$2$ becomes O$($n$2).$