This is actually just standard theory. They teach this in every undergrad algorithms class. A lot of it is just getting good intuition for these sorts of proble

This is actually just standard theory. They teach this in every undergrad algorithms class. A lot of it is just getting good intuition for these sorts of problems. For example, the nth Fibonacci number has n log_2 \phi bits, which means that to simply list the digits in the nth number, it takes O(n) time. So from there it's pretty easy to see that actually this algorithm can't "really" operate in O(log n), or at least, something must be up that causes us to produce that analysis. Another bit of intuition that might help you see where this bound comes from: what's actually true is that it takes O(log n) _matrix multiplications_ to get the result. So if you see that and you see that listing the digits of the nth number of the sequence is O(n), it starts to point at the fact that there's a hidden cost to the multiplications.