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?
Best Answer
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$.