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.