Master Theorem: $T(n) = 3T(\frac{n}{3} − 2) + \frac{n}{2}$ 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?
 A: 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)$.
A: 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,
