I'm stuck trying to solve the following recurrence:
$$\begin{align*} T(n) &= 4T(\frac n 2 + 2) + n : n > 8\\ T(n) &= 1 : n \leq 8 \end{align*}$$
In particular, I'm not sure how to deal with the expression $T(\frac n 2 + 2)$. I'm trying to use a recursion tree. I've found that the "cost" at the $k$th level of the tree is
$$4^k\left(\frac n {2^k} + \sum^k_{i = 1} 2^{2- i}\right)$$
by looking at the cost of the first few levels of the tree, which I understand to be:
$$4(\frac n 2 + 2)\\ 16(\frac n {2^2} + 2 + 1)\\ 64(\frac n {2^3} + 2 + 1 + \frac 1 2)\\ 256(\frac n {2^4} + 2 + 1 + \frac 1 2 + \frac 1 4)$$
etc. So the whole cost would be
$$T(n) = \sum_{k = 1}^{\log_2 n} 4^k\left(\frac n {2^k} + \sum^k_{i = 1} 2^{2- i}\right)$$
but I'm not at all clear how to go from this to a nice, closed-form expression, or how to deal with the value of $T(n)$ over the range $[0, 8]$.
What's the right way to approach this?
For the complementary solution part,
$T_c(n)=4T_c\left(\dfrac{n}{2}+2\right)$
$T_c(2^n+4)=4T_c\left(\dfrac{2^n+4}{2}+2\right)$
$T_c(2^n+4)=4T_c(2^{n-1}+4)$
$T_c(2^n+4)=4^nC$
$T_c(n)=(n-4)^2C$
For the particular solution part,
Let $T_p(n)=An+B$ ,
Then $An+B-4\left(A\left(\dfrac{n}{2}+2\right)+B\right)\equiv n$
$-An-8A-3B\equiv n$
$\therefore\begin{cases}-A=1\\-8A-3B=0\end{cases}$
$\begin{cases}A=-1\\B=\dfrac{8}{3}\end{cases}$
$\therefore T(n)=(n-4)^2C-n+\dfrac{8}{3}$
$T(8)=1$ :
$16C-\dfrac{16}{3}=1$
$C=\dfrac{19}{48}$
$\therefore T(n)=\dfrac{19(n-4)^2}{48}-n+\dfrac{8}{3}$