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 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 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)$.
First, note that there's (almost) no solution to your recurrence as stated. For example, starting with $n=7$ we have $$ \begin{align} T(7)&=4T(5.5)+7\\ &=4(4T(4.75)+5.5)+7=16T(4.75)+22+7\\ &=64T(4.375)+76+22+7 \end{align} $$ You get the picture. As we continue this process, the arguments get closer to 4 but never reach 4, so unless you define $T(x)$ for some $x$ in this sequence, you'll have a divergent calculation.
All is not lost, though, since we can slightly modify your recurrence to $$ T(n)=4T\left(\left\lfloor\frac{n}{2}\right\rfloor+2\right)+n \qquad\qquad\qquad\text{(*)} $$ and observe that we'll have $T(4)=4T(\lfloor4/2\rfloor+2)+4=4T(4)+4\text{, so }T(4)=-4/3$ and we can stop the recursive calls at $n=4$. What I'm about to do can be generalized to recurrences where the argument is $(\lfloor n/a\rfloor+b)$, but I hope the answer for this particular recurrence will suffice.
The trick here is to compute $T(2^k)$ for $k>2$. First, consider just the argument to $T$. We'll have $$ \begin{align} 2^k&=2^k\\ \left\lfloor\frac{2^k}{2}\right\rfloor+2&=2^{k-1}+2\\ \left\lfloor\frac{2^{k-1}+2}{2}\right\rfloor+2&=2^{k-2}+1+2\\ \left\lfloor\frac{2^{k-2}+1+2}{2}\right\rfloor+2&=2^{k-3}+1+2\\ \left\lfloor\frac{2^{k-3}+1+2}{2}\right\rfloor+2&=2^{k-4}+1+2\\ \end{align} $$ and so except for the first two terms, each subsequent argument will be of the form $2^{k-j}+3$. Now let's expand $T(2^k)$, using our recurrence (*) above: $$ \begin{align} T(2^k)&=4T(2^{k-1}+2)+2^k\\ &=4(4T(2^{k-2}+3)+(2^{k-1}+2))+2^k\\ &=4^2T(2^{k-2}+3)+4(2^{k-1}+2)+2^k\\ &=4^2(4T(2^{k-3}+3)+(2^{k-2}+3))+4(2^{k-1}+2)+2^k\\ &=4^3T(2^{k-3}+3)+4^2(2^{k-2}+3)+4(2^{k-1}+2)+2^k \end{align} $$ and by now the pattern should be clear. We'll have $$ \begin{align} T(2^k)&=4^jT(2^{k-j}+3)+4^{j-1}(2^{k-j+1}+3)+\cdots+4(2^{k-1}+2)+2^k\\ T(2^k)&=4^jT(2^{k-j}+3)+4^{j-1}(2^{k-j+1}+3)+\cdots+4(2^{k-1}+3)+(2^k+3)-7 \end{align} $$ Now we stop calculation when the argument $2^{k-j}+3=4\text{, namely when }j=k$, giving us $$ \begin{align} T(2^k)&=4^kT(4)-7+\sum_{i=0}^{k-1}4^i(2^{k-i}+3)\\ &=4^k(-\frac{4}{3})-7+2^k\sum_{i=0}^{k-1}2^i+3\sum_{i=0}^{k-1}4^i\\ &=4^k(-\frac{4}{3})-7+2^k(2^k-1)+3\frac{4^k-1}{3}\\ &=\frac{2}{3}(2^k)^2-2^k-8 \end{align} $$ so we conclude that when $n$ is a power of 2 we have $$ T(n)=\frac{2}{3}n^2-n-8 $$ We're almost done. Once we establish that $T(4),T(5), T(6), \dots$ is a strictly increasing sequence (which isn't that hard to do) we can conclude that for $2^{k-1}<n\le2^k$, $$ \frac{2}{3}2^{2(k-1)}-2^{k-1}-8 < T(n) \le \frac{2}{3}2^{2k}-2^k-8 $$ and so we finally come to the theta bound you wanted, namely $T(n)=\Theta(n^2)$.
Fun problem, Thanks for posing it.
