Use a recursion tree to determine a good asymptotic upper bound on the recurrence \(T(n) = T(n - 1) + T(n/2) + n\). Use the substitution method to verify your answer.
This problem is pretty interesting and at the same time quite difficult.
Also I’ll deviate from my usual approach of solving earlier exercises in this chapter, as there are two branches at each level of this recurrence which grows quite differently.
Getting an upper bound is easy, as we can find a recurrence that definitely grows much faster than this one. But finding a tight upper bound is tricky.
Just An Upper Bound
Note that, asymptotically,
\[T(n) = T(n - 1) + T(n/2) + n \le 2T(n - 1) + n\]And the above holds as long as we choose \(n \ge 2\).
Now the recurrence tree for the larger recurrence (the right one) of the above:
Rate of increase in number of subproblems in each recursion = 2
Rate of decrease in subproblem size = 1 with 1 less input
Hence at depth \(i = 0, 1, 2, \dots, n\) of the tree, there are \(2^i\) nodes each of cost \((n - i)\).
Hence, total cost of the tree is:
\[\begin {aligned} T(n) & = \sum_{i = 0}^{n} 2^i \cdot (n - i) \\ & = n\sum_{i = 0}^{n} 2^i - \textcolor {blue} {\sum_{i = 0}^{n} i \cdot 2^i} \end {aligned}\]The second sum in the above equation (highlighted in blue) can be computed in many ways. Here is one such method:
\[\begin {aligned} S &= 1 \cdot 2^1 + &&2 \cdot 2^2 + \cdots + &(n - 1)& \cdot 2^{n - 1} + &n& \cdot 2^n \\ 2S &= &&1 \cdot 2^2 + \cdots + &(n - 2)& \cdot 2^{n - 1} + &(n - 1)& \cdot 2^n &&+ n \cdot 2^{n + 1} \\ S - 2S &= 1 \cdot 2^1 + &&1 \cdot 2^2 + \cdots + &1& \cdot 2^{n - 1} + &1& \cdot 2^n &&- n \cdot 2^{n + 1} \end {aligned}\]Simplifying further:
\[\begin {aligned} S &= n \cdot 2^{n + 1} - (2^1 + 2^2 + \cdots + 2^n) \\ &= n \cdot 2^{n + 1} - (2^0 + 2^1 + 2^2 + \cdots + 2^n) + 2^0 \\ &= n \cdot 2^{n + 1} - \sum_{i = 0}^{n} 2^i + 1 \\ \end {aligned}\]Going back to our recurrence cost:
\[\begin {aligned} T(n) & = \sum_{i = 0}^{n} 2^i \cdot (n - i) \\ & = n\sum_{i = 0}^{n} 2^i - \textcolor {blue} {\sum_{i = 0}^{n} i \cdot 2^i} \\ & = n\sum_{i = 0}^{n} 2^i - \textcolor {blue} {\left(n \cdot 2^{n + 1} - \sum_{i = 0}^{n} 2^i + 1\right)} \\ & = (n + 1) \cdot \sum_{i = 0}^{n} 2^i - n \cdot 2^{n + 1} - 1 \\ & = (n + 1) \cdot \frac {2^{n + 1} - 1} {2 - 1} - n \cdot 2^{n + 1} - 1 \\ & = (n + 1) \cdot (2^{n + 1} - 1) - n \cdot 2^{n + 1} - 1 \\ & = n \cdot 2^{n + 1} - n + 2^{n + 1} - 1 - n \cdot 2^{n + 1} - 1 \\ & = 2^{n + 1} - n - 2 \\ & \le 2^{n + 1} \\ & \le c2^n \\ \end {aligned}\]The last step holds as long as \(c \ge 2\) and \(n \ge 0\).
So, \(T(n)\) is definitely \(O(2^n)\) and we can use this as an initial guess to show this holds true using the substitution method.