Could Master Theorem be applied to this recurrence relation?

Question

I have the following recurrence relation

$T(n) = 4T(\frac{n+4}{2}) + n$

Is there some way in order to apply the Master Theorem to it?

Or do I have to find an alternative approach in order to solve it?

Answer 1

No, it does not apply as it is. I would recommend using another method (if only to diversify your toolkit), but if you really like the Master Theorem, you can do the following: define $T'$ as $$ T'(n) = T(n+m), \forall n\geq 1 \tag{1} $$ where $m$ is a constant to be determined later (spoiler: we will choose $m=4$). Then $$\begin{align} T'(n) &= T(n+m) = 4T\left(\frac{n+m+4}{2}\right) + (n+m)\\ &= 4T\left(\frac{n}{2}+\frac{m+4}{2}\right) + (n+m)\\ &= 4T'\left(\frac{n}{2}+\frac{m+4}{2}-m\right) + (n+m)\\ &= 4T'\left(\frac{n}{2}\right) + (n+m) \end{align}$$ where the last equality follows from choosing $m$ such that $\frac{m+4}{2}-m=0$, i.e. $m\stackrel{\rm def}{=} 4$.

So now, solve your recurrence relation for $T'$ using the Master theorem: $$ T'(n) = 4T'\left(\frac{n}{2}\right) + n+4 \tag{2} $$ and then use (1) to get back to $T$.

---

Detail: I ignored issues of floors and ceilings in the recurrence relation, as usual, for simplicity (note that the OP's question does the same). It can be shown that this will not change anything (as per the standard arguments), e.g. assuming $T$ is well-behaved (monotone).