Solving a recurrence relation using master method

Question

I know that the Master theorem is used for the recurrence relations of the form: $$T(n) = aT(n/b) + f(n)$$ In my question, I am supposed to solve the following recurrence relation by using Master theorem: $$T(n) = 2T(n/7) + 5T(n/8) + n$$ Can I take $f(n)=n$ and since $f(n)=\Theta(n^{\log_ba})$, can I say $T(n)$ is $O(n\log n)$? But if I do this, I neglect the fact that the relation must be of the form $T(n) = aT(n/b) + f(n)$. What should I do? Thanks.

Answer 1

Hint: Check that $T(n)\geqslant n$ and that each property $T(n)\leqslant cn$ is hereditary if $c\geqslant56/5$.

Choosing $c$ large enough, one gets $n\leqslant T(n)\leqslant cn$ for every $n$, in particular, $T(n)=\Theta(n)$.

Answer 2

You cannot directly apply the Master Theorem (in the form of the three cases) here (though there are other ways to find the asymptotic bounds of such a recurrence, including the elegant hint given in the answer by @Did). However, you can use a generalization of the Master theorem, known as the Akra-Bazzi method. You can also have a look at these notes.

In your case, the recurrence relation solves to $\Theta(n)$. Here is how:

$a_1 = 2, b_1 = 7, a_2 = 5, b_2 = 8$

$f(n) = n = \Omega(n) = \Theta(n)$, hence $c = d = 1$.

Now, you need to find a $\rho$ such that $\frac{2}{7^\rho} + \frac{5}{8^\rho} = 1$. This has no analytical solutions, but you can see that $0 < \rho < 1$. Then, $$\int_1^n\frac{f(u)}{u^{\rho + 1}}du = \int_1^n u^{-\rho}du = \frac{n^{1-\rho} - 1}{1 - \rho} = \Theta(n^{1 - \rho})$$ Therefore, the solution is: $$T(n) = \Theta(n^\rho(1 + \Theta(n^{1 - \rho})) = \Theta(n)$$

Edit: Of course, if $T(n) = \Theta(n)$, then it is also in $O(n\log n)$ or $O(n^2)$ etc.