# Solving a recurrence relation using master method

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.

-

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

-
No, the answer is T(n)=Θ(nlogn), the questions says this and wants us to show this using master method –  bigO Mar 3 '13 at 16:11
$\Theta(n\log n)$ is wrong, if your textbook says this, burn your textbook. $O(n\log n)$ is correct, I have no idea how to adapt the proof of the optimal result I presented, to this weaker result (and no desire to do so). Sorry. –  Did Mar 3 '13 at 16:13
I am not really sure about this but maybe you can take the approximation 5T(n/8) <= 5T(n/7) since it's an increasing function. and then the obvious steps follow. –  sukunrt Mar 3 '13 at 16:14
@sukunrt Impressive mind reading. (But I do not want to introduce artificially a log degeneracy where there is none.) –  Did Mar 3 '13 at 16:15
To be really pedantic about it O(n) is O(nlgn) :D. but jokes apart stupid solution in the textbook @Did's solutions is a correct tighter bound. –  sukunrt Mar 3 '13 at 16:15

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.

-