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

  • $\begingroup$ No, the answer is T(n)=Θ(nlogn), the questions says this and wants us to show this using master method $\endgroup$ – Yasin Razlık Mar 3 '13 at 16:11
  • $\begingroup$ $\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. $\endgroup$ – Did Mar 3 '13 at 16:13
  • $\begingroup$ 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. $\endgroup$ – sukunrt Mar 3 '13 at 16:14
  • $\begingroup$ @sukunrt Impressive mind reading. (But I do not want to introduce artificially a log degeneracy where there is none.) $\endgroup$ – Did Mar 3 '13 at 16:15
  • $\begingroup$ 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. $\endgroup$ – 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.


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.