Solving constants in the recursive term with master theorem

We are learning how to solve recurrence relations in different ways (Forward Substitution, Backward Substitution, Master Theorem, etc...). I really thought I understood the topic since most of the problems were in the form of $$aT(\frac{n}{b}) + f(n)$$ where applying the Master Theorem is no sweat, but we're given this recurrence relation wherein there is a constant inside the recursive term, I am not sure anymore if Master Theorem would still work, or is there another way?

\begin{align*} T(n) = 3T\left(\frac{n}{3}-2\right) + \frac{n}{2} \end{align*}

This one has a constant 2 inside the term, and I don't know how to show that this recurrence relation is upper bounded by $$O (n \log n)$$.

If you are just interested in an upper bound you can notice that $$T(n) \le S(n)$$ where $$S(n) = 3 S(n/3) + \frac{n}{2}$$ and has solution $$S(n) = O(n \log n)$$.

Alternatively there is always induction. You can show that, for $$n \ge 2$$, $$T(n) \le c n \log n$$.

For $$2 \le n < 7$$, $$T(n)$$ is a constant and $$n \log n \ge 1$$. Therefore the claim is true for a sufficiently large (constant) value $$c^*$$ of $$c$$.

For $$n \ge 7$$ you have: $$T(n) = 3T\left(\frac{n}{3} - 2\right) + \frac{n}{2} \le 3 c \frac{n}{3} \log \frac{n}{3} + \frac{n}{2} = cn \log n - cn \log 3 + \frac{n}{2},$$

which is at most $$cn \log n$$ when $$c n \log 3 \ge \frac{n}{2}$$ or, equivalently, $$c \ge \frac{1}{2 \log 3}$$.

Simply pick $$c = \max\{c^*, \frac{1}{2 \log 3} \}$$.

• How can we use Master Theorem on this recurrence relation? Mar 27 '21 at 19:20
• @lambduh you cannot apply Master's Theorem directly given this form of T(n) with a constant in the recurrence. You need to make some transformation to make it Master's Theorem applicable. As is the case Steven does with the fact that $T(n) \leq S(n)$ and we apply Master's Theorem for $S(n)$ and the big oh bound can then be applied to $T(n)$ based on the observation... Or you need to apply substitution and make a good guess $(T(n) \in O(n\log n))$ and proceed Mar 27 '21 at 19:23
• I just noticed, for the claim $2 \leq n < 7, T(n)$ is a constant and $n \log n \geq 1$, when $n = 2$, $n\log n = 2\log 2 < 1$. Mar 28 '21 at 3:46
• This contradicts $n\log n \geq 1$. Mar 28 '21 at 3:52
• Usually a $\log$ with unspecified base refers to the binary logarithm so $2 \log 2 = 2$. Besides, what is actually needed in the induction proof is $n \log n > 0$ which is true for any $n > 1$ and any base of the logarithm greater than $1$. Mar 28 '21 at 10:15

Akra and Bazzi proved a generalization of the master theorem which, in particular, implies that the formulas in the master theorem remain true even if you're adding some "noise" of the form you consider. In fact, the Akra–Bazzi theorem can handle noise of magnitude $$O\bigl(\frac{n}{\log^2 n}\bigr)$$.