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.

#### Recursion Tree

Rate of increase in number of subproblems in each recursion = 4

Rate of decrease in subproblem size = 2 with additional 2 inputs

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

Hence, total cost of the tree is:

\begin {aligned} T(n) & = \sum_{i = 0}^{\lg n} 4^i \cdot \left(\frac n {2^i} + 2\right) \\ & = \sum_{i = 0}^{\lg n} 4^i \cdot \frac n {2^i} + \sum_{i = 0}^{\lg n} 4^i \cdot 2 \\ & = n \sum_{i = 0}^{\lg n} \frac {4^i} {2^i} + 2 \sum_{i = 0}^{\lg n} 4^i \\ & = n \sum_{i = 0}^{\lg n} 2^i + 2 \sum_{i = 0}^{\lg n} 4^i \\ & = n \frac {2^{\lg n + 1} - 1} {2 - 1} + 2 \frac {4^{\lg n + 1} - 1} {4 - 1} \\ & = n (2^{\lg n + 1} - 1) + \frac {2} 3 (4^{\lg n + 1} - 1) \\ & = n (2 \cdot 2^{\lg n} - 1) + \frac {2} 3 (4 \cdot 4^{\lg n} - 1) \\ & = n (2 \cdot n - 1) + \frac {2} 3 (4 \cdot n^2 - 1) \\ & = 2n^2 - n + \frac {8n^2} 3 - \frac {2} 3 \\ & = O(n^2) \end {aligned}

#### Verification Using Substitution

Let’s assume, $$T(n) \le cn^2$$, for all $$n \ge n_0$$, where $$c$$ and $$n_0$$ are some positive constants.

\begin {aligned} T(n) & = 4T(n/2 + 2) + n \\ & \le 4c(n/2 + 2)^2 + n \\ & = 4c(n^2/4 + 2n + 4) + n \\ & = cn^2 + 8cn + 16c + n \\ & = cn^2 + (8c + 1)n + 16c \end {aligned}

We really cannot prove our assumption from the above. So let us modify our assumption by subtracting a lower order term.

Let’s assume, $$T(n) \le cn^2 - bn$$, for all $$n \ge n_0$$, where $$c$$, $$b$$ and $$n_0$$ are some positive constants.

\begin {aligned} T(n) & = 4T(n/2 + 2) + n \\ & \le 4(c(n/2 + 2)^2 - b(n/2 + 2)) + n \\ & = 4c(n^2/4 + 2n + 4) - 4b(n/2 + 2)) + n \\ & = cn^2 + 8cn + 16c - 2bn - 8b + n \\ & = cn^2 - bn - bn + 8cn + n + 16c - 2b \\ & = cn^2 - bn - (bn - 8cn - n - 16c + 2b) \\ & \le cn^2 - bn \end {aligned}

The last step holds as long as $$(bn - 8cn - n - 16c + 2b) \ge 0$$.

In other words, $$n \ge (16c - 2b)/(b - 8c - 1) \ge 0$$.

We can pick $$b$$ and $$c$$, and set $$n_0$$ using above equation.