Yes you could. For a fixed-width register machine you can go even further and say that there don't exist non-trivial constant time algorithms (it takes at least

Yes you could. For a fixed-width register machine you can go even further and say that there don't exist non-trivial constant time algorithms (it takes at least logarithmic time to read the entire input). This includes bread-and-butter classics like hashtables. In practice we usually hand-waive those details away because they don't apply on the domain of interest; rarely is somebody meaningfully exceeding a 64-bit space for their hashtables. You can formalize that a bit with something like the "Word RAM" model of computation -- assume that you have fixed width registers as wide as your inputs. For the Fibonacci sequence those details are a little harder to hand-waive away because of how quickly the output grows. As soon as the input is bigger than ~64 on a modern computer you'll start to see the effects of that linear runtime. On most clusters you'd have to stream Fib(1<<64) just to see all the bits, and it'd take ages. The reason that idea doesn't (usually) get applied to algorithms involving multiplication is because usually we're operating implicitly in a model that includes constant-time multiplication of "big enough" numbers. In cryptography and other fields operating on large integers though that analysis absolutely does come into play. The overarching theme is that reality is hard to capture both succinctly and accurately, and you want as simple of a model as possible that adequately describes the behavior you're curious about. Often that includes constant-time multiplication, but that'd seriously deceive you in an analysis of Fibonacci runtime.