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?
Asked
Active
Viewed 4,578 times
1 Answers
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$.
Anonymous
- 5,789
-
So if it would have been for instance $T(n) = T(n-c) + ...$, where c is a constant it would still have been n ? – trickster Jun 17 '18 at 23:10
-
@trickster It would have been $\Theta(n/c)$, so still linear in $n$. – Anonymous Jun 17 '18 at 23:30
-