I have a recursive equation that does not apply to the master method, since there is subtraction in the equation. I'd like to use the substitution method, but I have no idea where to start. Could anyone help me figure out how to start a problem when the master method does not apply?
This is the equation. T(n) = 3T(n/3-2) + n/2
I was thinking that maybe I could "guestimate" the bounds. I know that T(n) = 3T(n/3) + n is larger than my equation and meets the master method, so the upper bound on my equation would have to be less than T(n) = nlogn ? However, even if this is on the right track, I would still need to find a lower bound and I have no idea if nlogn would be a tight bound
Not an answer per se, but I'm not sure how to answer: Here is what I got:
Suppose $T:\Bbb{R}\rightarrow\Bbb{R}$ and that $T$ is constant on some interval $I_0=[a,b]$, with $T(I_0) = c$. Then by recursion $T$ is defined on $$I_n = [3(3^n-1)+3^n a,3(3^n-1)+3^n b],$$ further $$T(x|x \in I_n)=\frac{3}{4}(1+2n-3^n)+3^n c+ \frac{n x}{2}$$
So $T$ is linear in each segment where it's defined but the constant of proportionality changes (slowly). Setting $c=3/4$ is a natural choice leading to a simpler formula for $T$.
$$T(x|x \in I_n)=\frac{3}{4}+ \frac{n(3+x)}{2}$$
I'm not really sure what else you wanted to know about $T$.