Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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