n^th Fibonacci number requires O(n) bits. So, saying the solution is O(log(n)) is kinda not true. I mean there cannot be a o(n) algorithm for computing decimal representation of n^th fibonacci number.
As always, it depends on your computational model. People are awful at specifying a model, in other words it's unclear what's even being stated.
You can compute the nth fibonacci number in O(lg n) additions and multiplies. That indeed doesn't turn out to be a good model for how long it takes on an actual computer though.
And even if the model is sufficiently specified, the constant factors and lower terms hidden in the O-notationen can be deciding in practice, and are yet usually left out.
You can compute the nth fibonacci number in O(lg n) additions and multiplies. That indeed doesn't turn out to be a good model for how long it takes on an actual computer though.