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.
Recursion Tree
Ignoring the floor function, the recursion takes the form:
\[T(n) = 3T(n/2) + n\]Rate of increase in number of subproblems in each recursion = 3
Rate of decrease in subproblem size = 2
Hence at depth \(i = 0, 1, 2, \dots, \lg n\) of the tree, there are \(3^i\) nodes, each of cost \(n/2^i\).
Hence, total cost of the tree is:
\[\begin {aligned} T(n) & = \sum_{i = 0}^{\lg n} 3^i \frac n {2^i} \\ & = n \cdot \sum_{i = 0}^{\lg n} \left(\frac 3 2\right)^i \\ & = n \cdot \frac {(3/2)^{\lg n + 1} - 1} {(3/2) - 1} \\ & = 2n \cdot ((3/2)\cdot(3/2)^{\lg n} - 1) \\ & = 3n \cdot (3/2)^{\lg n} - 2n \\ & = 3n \cdot \frac {3^{\lg n}} {2^{\lg n}} - 2n \\ & = 3n \cdot \frac {3^{\lg n}} n - 2n \\ & = 3 \cdot 3^{\lg n} - 2n \\ & = 3 \cdot n^{\lg 3} - 2n \\ & = O(n^{\lg 3}) \end {aligned}\]The last step comes from the fact that \(n^{\lg 3} \approx n^{1.58} > n\).
Verification Using Substitution
If you notice carefully, the recurrence has almost exact same form (ignoring floor) as the modified recurrence in the previous exercise after changing variables.
We can follow the substitution method of that exercise to verify this as.