What is the time complexity of computing Fibonacci(n) recursively (without memoisation)?

Question

Accepted Answer

(C) O(2^n). Explanation: Without memoisation, fib(n) makes exponentially many calls — O(2^n) in the worst case.