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