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?

  • $\begingroup$ The vanilla version of the Master theorem will not. However, you can start by applying it to the same relation without the $+4$, see what it gives, and then apply e.g. substitution to your original relation to see if the solution is roughly the same. (i.e., "having $T(n/2+2)$ instead of $T(n/2)$ shouldn't morally change anything." But trying a different method altogether would probably be best. $\endgroup$ – Clement C. Jun 8 '16 at 17:06
  • $\begingroup$ @ClementC. without the $+4$, Master Theorem gives $T(n) = \Theta(n^2)$. But I didn't quite understand what you meant with "apply e.g. substitution to your original relation to see if the solution is roughly the same" $\endgroup$ – Da Mike Jun 8 '16 at 17:14
  • $\begingroup$ You have a candidate solution $cn^2$ or so. Now, use the substitution method to see if it's indeed a solution to the original relation. $\endgroup$ – Clement C. Jun 8 '16 at 17:16

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

| cite | improve this answer | |
  • $\begingroup$ Got it. Thanks! $\endgroup$ – Da Mike Jun 8 '16 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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