Technically, Fib(n) at unbounded sizes is at least linear to compute. This is because the output of Fib(n) has O(n) bits in it. So even if the computation is free, it's still O(n) just to print the result.

That's not the type of thing I would ever expect a candidate to know in an interview, just something fun I've run across.