Minus One Not Half

Someone applies the master theorem to $T(n) = T(n-1) + T(n-2) + 1$ , reads off $a = 2$ and $b = 1$ , and concludes $\Theta(n)$ . What went wrong, and what is the real answer?

The tree has depth $n$ and each level costs $O(1)$ , so $\Theta(n)$ is right by accident.

The theorem covers $T(n) = aT(n/b) + f(n)$ , where subproblems shrink by a constant factor. These shrink by a constant amount, so no $b$ exists and $b = 1$ is meaningless. The solution is $\Theta(\varphi^n)$ with $\varphi = (1+\sqrt5)/2$ .

The setup is fine but the wrong case was chosen; case 2 gives $\Theta(n \log n)$ .

$\Theta(2^n)$ . Every call makes two more, so the tree is a complete binary tree of depth $n$ .