# Master Theorem Usage

I know how to use the master Theorem for a general formula e.g. $T(n) = a \cdot T(\frac{n}{b}) + f(n)$.

I saw some books suggest that we can use the mastere theorem for formulas like: $T(n) = T(\frac{n}{5}) + T(\frac{7n}{10}) + O(n)$

How is that possible?

My guess: We use it separately. Once for $T(n) = T(\frac{n}{5}) + O(n)$ and once for $T(n) = T(\frac{7n}{10}) + O(n)$ and join between.

Thanks!

• Which books "suggest" that? Please quote the passages with attribution. How would you "join between"? – Raphael Sep 10 '17 at 19:30
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Sep 10 '17 at 19:30
• You might be interested in this reference question. – Raphael Sep 10 '17 at 19:30

Basically we can look at the fractional terms inside the recurrence calls. If the sum to less than $n$, then the "conquer" part of "divide-and-conquer" will dominate the "divide" part.
For your example we have the fractions: $\frac{n}{5} + \frac{7n}{10} = \frac{9n}{10} < n$. Therefore the $O(n)$ term will dominate and the overall time complexity will be $\Theta(n)$. This is an idea of the Master Theorem, figuring out which dominates: "divide" or "conquer". Again, I highly suggest looking at this answer for a more in-depth proof.