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

  • 1
    $\begingroup$ 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. $\endgroup$
    – Paresh
    Mar 3, 2013 at 17:08
  • $\begingroup$ For this kind of recurrence you have to expand things by hand and look for some patterns. It is ugly. $\endgroup$ Mar 3, 2013 at 17:43
  • 1
    $\begingroup$ You can also "guess" the right answer and prove the result by induction. $\endgroup$
    – Joe
    Mar 4, 2013 at 4:04

2 Answers 2


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.

  • $\begingroup$ How do you find p? $\endgroup$ Feb 2, 2015 at 3:39
  • $\begingroup$ Usually, you are not able to find a closed-form solution for $p$, so you have to solve numerically. $\endgroup$ Feb 2, 2015 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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