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$$.