Complexity Analysis
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)What is the time and space complexity?
Work it out before scrolling down.
Time
O(2ⁿ)
Space
O(n)
How to derive it
Each call spawns two more calls, creating a binary tree of calls. The tree has depth n and roughly 2ⁿ nodes → O(2ⁿ) time. But space is only O(n) — at any moment, only one branch is active on the stack (depth n). The tree is wide but the stack is deep, not wide.