# Usage of master theorem for solving recursions

I know that master theorem is used for the recurrence relations of the form:

T(n) = aT(n/b) + f(n)

But 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)=Θ(nlogba), i say T(n) is O(nlogn)? 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

• Cross-posted: math.stackexchange.com/questions/319535/…. Please do not cross-post immediately on two stackexchange sites. Wait for a few days, and if you do not get an answer, you can post at another place with links to the other question in both posts. – Paresh Mar 3 '13 at 17:08
• For this kind of recurrence you have to expand things by hand and look for some patterns. It is ugly. – Pratik Deoghare Mar 3 '13 at 17:43
• You can also "guess" the right answer and prove the result by induction. – Joe Mar 4 '13 at 4:04

You may solve this recurrence by using the Akra-Bazzi method, which generalizes the master theorem and allows solving recurrences of the form

$T(n)= \sum\limits_{i = 1}^k {a_i T(n/b_i) + f(n)}$

You need to solve for $p$ the equation

$\sum\limits_{i = 1}^k {a_i b_i^{-p} = 1}$

and the solution to the recurrence can be obtained exactly as in the master theorem, but you must compare $f(n)$ with $n^p$ instead of $n^{\lg_b a}$.

For your recurrence, $p = 0.954101 \quad$ so that $f(n) = n \quad$ dominates $n^p = n^{0.954101}$ and therefore, $T(n) = O(n) \quad$ (you may want to verify that the master theorem regularity condition also holds).

Akra and Bazzi also proved a more general result.

• How do you find p? – Zach Saucier Feb 2 '15 at 3:39
• Usually, you are not able to find a closed-form solution for $p$, so you have to solve numerically. – Massimo Cafaro Feb 2 '15 at 7:14

Well, you can easily get $T(n)=O(n\log n)$, since $2T(n/7)+5T(n/8)\le 7T(n/7)$, and the master theorem gives you that $S(n)=7S(n/7)+n$ is $\Theta(n\log n)$.

The question is, can you do better - that is to prove that $T(n)=\Theta(n)$. I think that if you follow the proof of the master theorem, you will be able to conclude that.