4
$\begingroup$

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

$\endgroup$
  • 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 '13 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$ – Pratik Deoghare Mar 3 '13 at 17:43
  • 1
    $\begingroup$ You can also "guess" the right answer and prove the result by induction. $\endgroup$ – Joe Mar 4 '13 at 4:04
5
$\begingroup$

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.

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

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.

$\endgroup$

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.