# 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?

-

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.

-

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)$.

-