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 F

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 :)