1
$\begingroup$

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

$\endgroup$

2 Answers 2

2
$\begingroup$

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} \}$.

$\endgroup$
7
  • $\begingroup$ How can we use Master Theorem on this recurrence relation? $\endgroup$
    – lambduh
    Mar 27, 2021 at 19:20
  • $\begingroup$ @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 $\endgroup$ Mar 27, 2021 at 19:23
  • $\begingroup$ 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$. $\endgroup$
    – lambduh
    Mar 28, 2021 at 3:46
  • $\begingroup$ This contradicts $n\log n \geq 1$. $\endgroup$
    – lambduh
    Mar 28, 2021 at 3:52
  • $\begingroup$ 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$. $\endgroup$
    – Steven
    Mar 28, 2021 at 10:15
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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