Solving recurrence relation of form $T(n/2 + c)$ It is obvious that the Master Theorem cannot be applied to the recurrences of the following form:
$T(n) = 4T(n/2 + 2) + n$
Since I am only interested in the $\theta$ bound of the recurrence and not the exact solution, what is the best way to approach this problem?
 A: A different (to Rick Decker's) approach is so attempt to find a "nice" function that satisfies this recurrence, and then see what variations are possible. We have the relation
$$T(n)=4T(n/2+2)+n$$
and we can get rid of the $2$ by a variable substitution $n=m+4$, so that
$$T(m+4)=4T(m/2+4)+m+4$$
and we can change this to a linear recurrence with substitution $m=2^t$
$$T(2^t+4)=4T(2^{t-1}+4)+2^t+4$$
and eliminate the multiplication by $4$ with the substitution $T(2^t+4)=4^tf(t)$
$$f(t)=f(t-1)+2^{-t}+4^{1-t}.$$
This looks like an exponential, so if we try (a.k.a. ansatz) the solution $f(t)=A+B2^{-t}+C4^{-t}$, we get
$$A+B2^{-t}+C4^{-t}=A+2B2^{-t}+4C4^{-t}+2^{-t}+4\cdot4^{-t}$$
$$(B-2B-1)2^{-t}+(C-4C-4)4^{-t}=0,$$
whence $B=-2$ and $C=-\frac43$. Unwinding our substitutions, we get
$$t=\lg m=\lg(n-4)\Rightarrow T(m+4)=m^2f(\lg m)=Am^2-2m-\frac43$$
$$T(n)=A(n-4)^2-2n-\frac{20}3$$
and we are nearly done. However, since this is a recurrence equation and not a differential equation, there are holes of unspecified behavior in between, and the solution for $f(t)$ would not be affected if a 1-periodic function $g(t)$ was added to it, so we find instead $T(m+4)=m^2g(\lg m)-2m-\frac43$. If we know $T(n)$ is continuous, then $g(n)$ is bounded, and we can say that $T(n)=\Theta(n^2)$. Otherwise, a function which is not $\Theta(n^2)$ and satisfies the recurrence is $T(m+4)=m^2\tan(\pi\lg m)-2m-\frac43$.
A: A different approach. Try the recursion tree method (consult CLRS)
$ T(n)=T(n/2+2)+n$
Using the tree we get, at level $i$, the sum as
$4^i c(n/2^i)+ 2*4^i $ stopping at $T(3)$ (assuming it to be a constant value).
It stops when $n=2^i$ and hence $i=\log n$ , Therefore summing the equation from $i=0$ to $i=\log n$ we get
$(2^{\log n} - 1) + (2^{2\log n}-1)/3 $ , which gives $\theta(n^2)$.
