# Constant terms at each level of a recursion tree

In CLRS, exercise 4.4-5 the following question is asked:

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$

In my recursion tree, the sum of level 0 is $$n$$ level 1 is $$(3/2)n - 2/2^1$$ level 2 $$(3/2)^2n-14/2^2$$ level 3 is $$(3/2)^3n - 74/2^3$$ and so on. My issues is that the rule governing the constants 2, 14, 74 etc. is difficult to express as a function of the level so that I can create a sum for all levels of the tree.

Would it be correct to say that the cost at each level of the tree is $$(3/2)^in - O(1)$$ and thus avoid the problem of having to sum all of the constant terms via big O notation, or is this approach incorrect? If so, why and what should I do instead?

For each specific level $$i$$, it is true that the cost is $$(3/2)^i n - O(1)$$. However it would be misleading to state this in general. Suppose for example that the cost at level $$i$$ were $$(3/2)^i n + 2^{2^i}$$, and that there were $$\log n$$ levels. The dominant factor in the total cost would be the "constant" term.
However, in your case, you can say that the cost at level $$i$$ is at most $$(3/2)^i$$, which gives you the required upper bound.
• You need to estimate them as a function of $i$. No way around it. – Yuval Filmus Feb 12 at 11:01
Regarding the recurrence itself. First, for concreteness, let us define $$T(0) = 0$$ and for $$n > 0$$, $$T(n) = T(n-1) + T(\lfloor n/2 \rfloor) + n.$$ Let $$S(n) = T(n) + 2n$$. Then $$S(n) = T(n) + 2n = T(n-1) + T(\lfloor n/2 \rfloor) + 3n = S(n-1) + S(\lfloor n/2 \rfloor) + n+1 - 2\lfloor n/2 \rfloor,$$ and $$S(0) = 0$$. Note that $$n+1-2\lfloor n/2 \rfloor \in \{1,2\}$$. Therefore if we define a $$R(0) = 0$$ and $$R(n) = R(n-1) + R(\lfloor n/2 \rfloor) + 1$$ then $$S(n) = \Theta(R(n))$$ and so $$T(n) = \Theta(R(n)) - 2n$$.
Now let $$U(n) = R(n) + 1$$. Then $$U(0) = 1$$ and $$U(n) = U(n-1) + U(\lfloor n/2 \rfloor).$$ Thus $$U(n)$$ is the number of ways to reach $$0$$ using two operations: subtract $$1$$ and right shift by $$1$$. Also, $$R(n) = U(n) - 1$$, and so $$T(n) = \Theta(U(n)) - 2n$$, which is going to equal $$\Theta(U(n))$$.
The sequence $$U$$ is also known as A000123, where other interpretations are given. The asymptotics of the sequence are known to be $$n^{\Theta(\log n)}$$. More accurate answers can be found on the OEIS references.