I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5):
$$T(n) = T(n - 1) + T(n/2) + n$$
The exercise asks you to find the upper bound using the recurrence-tree method. I tried drawing one. It would have $2^n$ leafs if it was a complete binary tree (the height is $n$), but it is not. Furthermore, I cannot find a formula that expresses the complexity of each level like they do in the book.
After writing some code to calculate $T(n)$ and comparing it with different functions, I end up thinking that the complexity is exponential. Using $c2^n$ with the substitution method works out, but I'm not certain that this is a tight bound. I'm not certain that the tight bound is exponential either.
Can somebody help me out through the reasoning?
P.S.: If it matters, I'm not in school/university and this is not homework. I'm a (let's say) Ruby programmer who is self-studying to fill in his gaps in Computer Science.
Not so.
A previous answer asserted correctly that $T(n)\geqslant\frac12n^2$ and wrongly that the property $T(n)\leqslant cn^2$ is hereditary (that is, if it holds for every $k\leqslant n-1$ it holds for $n$) for every $c\geqslant2$.
In fact, the property $T(n)\leqslant cn^2$ is not hereditary and the complexity is neither polynomial nor exponential. It seems that $\log T(n)\sim(\log n)^2/(2\log2)$ and one can probably check that, for every positive $\varepsilon$, the property $$ \exp((\log n)^{2-\varepsilon})\leqslant T(n)\leqslant\exp((\log n)^{2+\varepsilon}) $$ is hereditary for every $n$ large enough.