The number of bits in Fib(n) is O(n), not O(log n). Put differently, Fib(n) grows exponentially. To be precise, Fib(n) = (phi^n - (-phi)^(-n)) / sqrt(5). So the

The number of bits in Fib(n) is O(n), not O(log n). Put differently, Fib(n) grows exponentially. To be precise, Fib(n) = (phi^n - (-phi)^(-n)) / sqrt(5). So the complexity to compute Fib(n) is O(n) time (or slower). And one algorithm that runs this fast is to compute the n-th power of [[1,1],[1,0]] (using repeated squaring and large integer arithmetic).