2
$\begingroup$

Find the asymptotic bound in terms of $\Theta$ (Theta) using the master theorem for the following recursive equation. Assume that $t(n)= \Theta (1)$ for suffucuently small $n$. $$t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$$

I am a bit confused on how to approach such question, I did solve questions such as $t(n)=3t(n/4)+nlogn$, but never saw an example where $t(n)=at(\frac{n}{b})+ct(\frac{n}{d})+f(n)$.

Any solutions or hints on how to solve this problem would be appreciated.

$\endgroup$
2
$\begingroup$

If we are not restricted by "using the master theorem", then either a better version of the master theorem, the versatile Akra-Bazzi method or the elementary way to show many recurrence relations mean $\Theta(n)$ or $\Theta(n\ln n)$ is an easy approach.

Otherwise, let us see how we can use the master theorem. We assume here $t(n)\geq 0$ for all $n \geq 0$, although the final asymptotic answer is actually valid without that non-negativity restriction. Let $c$, $m$ be two positive constants such that $t(n) \lt m$ for all $n < c$.

To bound $t$ from below, let us define function $t_1$ by $$t_1(n) = \begin{cases} 0 & n <= c\\ t_1\left(\frac{n}{5}\right) + n & n\gt c \end{cases}$$

To bound $t$ from above, let us define function $t_2$ by $$t_2(n) = \begin{cases} m & n <= c\\ t_2\left(\frac{n}{5}\right) + (t_2\left(\frac{n}{5}\right) + m) + n & n\gt c \end{cases}$$

The rest of this solution will be proving $t_1(n)\leq t(n)\leq t_2(n)$ for all $n\ge 0$ by induction followed by applying the master theorem to $t_1$ and $t_2$ to show that $t(n) = \Theta(n)$. It is left as an easy exercise for interested readers.

$\endgroup$
  • $\begingroup$ One should note that this technique doesn't work as easily for all recurrences; as in proving the third case of the Master theorem, some conditions have to be fulfilled. (Here, e.g., $0 \leq T(n/17) \leq T(n/5)$ for "all" $n$.) $\endgroup$ – Raphael Aug 9 '18 at 6:31
  • $\begingroup$ @Raphael, I just corrected several serious typos. The condition you mentioned inside the parentheses should not be necessary any more (under the non-negativity assumption). Of course, we still need facts including 2 < 5 to apply the third case of the Master theorem in order to arrive at $\Theta(n)$. $\endgroup$ – John L. Aug 9 '18 at 11:53
  • $\begingroup$ @Raphael, by the way, I doubt this question is a duplicate since it asks/demands you to use the Master theorem explicitly. Unless you believe using Akra-Bazzi method can be counted as using the Master theorem, none of the 10 answers in the link would be considered as a proper answer. Anyway, thanks for your moderation! $\endgroup$ – John L. Aug 9 '18 at 12:07
  • $\begingroup$ Fair enough, reopened. $\endgroup$ – Raphael Aug 9 '18 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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