0
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Which books "suggest" that? Please quote the passages with attribution. How would you "join between"? $\endgroup$ – Raphael Sep 10 '17 at 19:30
  • 1
    $\begingroup$ 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! $\endgroup$ – Raphael Sep 10 '17 at 19:30
  • $\begingroup$ You might be interested in this reference question. $\endgroup$ – Raphael Sep 10 '17 at 19:30
1
$\begingroup$

You can use the idea of the Master Theorem and apply it to these occurrences. That is what I have done here, I would recommend looking at that answer because it will answer your question.

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.

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