Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 3T(\lfloor n/2 \rfloor) + n$. Use the substitution method to verify your answer.

Note: I will solve the problems in this section a bit differently than it was done in the book. In the chapter text, the authors have dealt the cost of the leaves separately and summed up the cost of the rest of the nodes. But I will find the cost of the whole tree at one go, without dealing any node separately. There won’t be any difference in the result.

Ignoring the floors, the recusrion takes the form:

Rate of increase in number of subproblems in each recursion = 3 Rate of decrease in subproblem size = 2

Hence in each level of the tree, there are $3^i$ nodes each of cost $cn/2^i$ at depth $i = 0, 1, 2, \dots, \lg n$.

Hence, total cost of the tree is:

The last step comes from the fact that $n^{\lg 3} \approx n^{1.58} > n$.

Now we have to show that our guess $T(n) = O(n^{\lg 3})$ holds using the substitution method. Let us refine our guess as $T(n) \le d(n^{\lg 3} - n)$ for some constant $d > 0$ (Note: I refined the guess to match it the exact form we got in the last but one step of summing the cost of the tree. Otherwise if we start with the guess $T(n) \le dn^{\lg 3}$, we won’t be able to prove anything and we have to subtract a lower order term).

The last step holds as long as $d/2 \ge 1$, i.e. $d \ge 2$.