Draw the recursion tree for \(T(n) = 4T(\lfloor n/2 \rfloor) + cn\), where \(c\) is a constant, and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method.
Ignoring the floors, the recursion takes the form:
\[T(n) = 4T(n/2) + cn\]Rate of increase in number of subproblems in each recursion = 4
Rate of decrease in subproblem size = 2
Hence at depth \(i = 0, 1, 2, \dots, \lg n\) of the tree, there are \(4^i\) nodes each of cost \(cn/2^i\).
Hence, total cost of the tree is:
\[\begin {aligned} T(n) & = \sum_{i = 0}^{\lg n} 4^i \cdot c\frac n {2^i} \\ & = cn \cdot \sum_{i = 0}^{\lg n} 2^i \\ & = cn \cdot \frac {2^{\lg n + 1} - 1} {2 - 1} \\ & = cn \cdot (2\cdot2^{\lg n} - 1) \\ & = cn \cdot (2n - 1) \\ & = 2cn^2 - cn \end {aligned}\]Asymptotic upper bound
\[\begin {aligned} T(n) & = 2cn^2 - cn \\ & \le 2cn^2 \\ & = O(n^2) \end {aligned}\]The last step holds as long as \(cn \ge 0\) and \(c \le n\).
For example, \(n \ge n_0 = 2\) and \(c = 1\).
Asymptotic lower bound
\[\begin {aligned} T(n) & = 2cn^2 - cn \\ & = cn^2 + (cn^2 - cn) \\ & \ge cn^2 \\ & = \Omega(n^2) \end {aligned}\]Last step holds as long as \((cn^2 - cn) \ge 0\).