The closed form solution is technically O(phi^N), so still exponential. It comes mostly from exponentiation not being constant time, see https://stackoverflow.com/questions/360748/computational-com.... It'll only be constant time if your values fit into a hardware register and you can leverage the exponentiation instructions of your CPU.

There is a O(log(N)) solution involving matrix exponentiation though, if you really need to get the big numbers.

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.