OK, I see this response is getting downvoted. Here's a PSA on arithmetic. The function n -> 2^n takes input of size O(log(n)) and returns output of size O(n).

OK, I see this response is getting downvoted. Here's a PSA on arithmetic. The function n -> 2^n takes input of size O(log(n)) and returns output of size O(n). Of course, n = 2^(log n), so our function takes exponential time/space in input size to simply write the output. The Fibonacci function is like that. Of course, discussions of complexity become cumbersome if you don't specify variables; that's why we talk about complexity in n of computing Fib(n). Potato, potato anyway.