Height of recursion tree

Question

If the recursion is of the form $T(n) = T(n/b) + ...$, the height of the recursion tree is $\log_b n$. My question is if the recursion of the form $T(n) = 2T(n-1) + ...$, the same formula still applies?

Answer 1

I would say that the question is not terribly clear, but if by "height" you mean the depth of the recursion, i.e. how many times you have to re-write your equation until your $T(\cdot)$ terms are all $T(O(1))$, the answer is that a recursion in the form $T(n)=2T(n−1)+f(n)$ has depth $n+O(1)$.

Note that you need to reduce your $n$ by a multiplicative constant bounded away from $1$ in order to make the number of levels logarithmic in $n$. Reduction by an additive constant, however large, keeps the number of levels linear in $n$.