Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.