Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
