Draw the recursion tree for $T(n) = 4T(\lfloor n/2 \rfloor) + cn$, where $c$ is a constant, and provide a tight assymptotic bound on its solution. Verify your bound by the substitution method.

Ignoring the floors, the recusrion takes the form:

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

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

Hence, total cost of the tree is:

Now, for assymptotic upper bound: %

And, for assymptotic upper bound: %

Last step holds as long as $n \ge 2$.