Only under the word-RAM model of computation though. The phrase "arithmetic operation" is doing a lot of heavy lifting. On a real computer, the output size of Fib is O(2^n), requiring O(n) bits of space, and O(n) assembly instructions (at a minimum, and for other reasons that minimum can be attained). The exponential nature of the problem additionally means you hit that Big-O curve for extraordinarily small inputs (as opposed to, e.g., a hash table where technically access isn't O(1) but nobody cares).

Separately though, that's a fun trick :)

That's why I phrased it that way. But since you mentioned working modulo 2^64, I thought that would count :-).

It's useful to make it explicit anyway for people who might miss that, so thanks!

oic. I missed that nuance. Thanks for the clarification.

Again, neat formula, happy to see your comments :)