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

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

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

Hence, total cost of the tree is:

Now we have to show that our guess $T(n) = O(n^2)$ holds using the substitution method. Let’s refine our guess to $T(n) \le d(n^2 - bn)$ for positive constants $b$ and $d$.

The last step holds as long as $db - 8d - 1 \ge 0$.