Master Theorem: $T(n) = 3T(\frac{n}{3} − 2) + \frac{n}{2}$

Question

I need to solve this recurrence using the Master Theorem; however, I don't know if its is possible since it doesn't follow the format

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

$a = 3$ $b = 3$? What happens to the -2 inside the recurrence?

Answer 1

Here's a start.

In $T(n) = 3T(\frac{n}{3} − 2) + \frac{n}{2} $, replace $n$ by $n+c$. I will choose $c$ so there is no offset.

$T(n+c) = 3T(\frac{n+c}{3} − 2) + \frac{n+c}{2} = 3T(\frac{n}{3}+\frac{c}{3} − 2) + \frac{n+c}{2} $ so if $c = c/3-2 $, or $c=-3$, this becomes $T(n-3) = 3T(\frac{n}{3}-3) + \frac{n-3}{2} $.

Let $U(n) = T(n-3)$. Then $U(n) =3U(n/3)+(n-3)/2 $.

Now solve this,

Answer 2

We need to modify $T$ to get get rid of the $-2$ in the recurrence. To do this we'll have to prove the upper bound and lower bound separately.

For the upper bound we have $T(n) = 3T(\frac{n}{3} - 2) + \frac{n}{2} \leq 3T(n) + \frac{n}{2}$. Master's theorem tells us that the recurrence $T'(n) = 3T'(\frac{n}{3}) + \frac{n}{2}$ has the solution $T'(n) = \Theta(n \log n)$, so $T(n) = O(n \log n)$.

For the lower bound, let's consider the function $S(n) = T(n + 6)$. We derive the following,

$$ \begin{align} S(n) &= T(n+6) \\\\ &= 3T(\frac{n+6}{3} - 2) + \frac{n}{2} \\\\ &= 3T(\frac{n}{3}) + \frac{n}{2}. \end{align} $$

We conclude that $S(n) \geq T(n)$. Again by Master's theorem we have $S(n) = \Theta(n \log n)$ and $T(n) = \Omega(n \log n)$, from which we conclude that $T(n) = \Theta(n \log n)$.