0
$\begingroup$

This question already has an answer here:

For instance, consider the following recurrence relation.

T(n) = T(n/2) + T(n/3) + T(n/4) + n

Would you use the substitution method for this?

$\endgroup$

marked as duplicate by D.W. Feb 13 '17 at 5:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Welcome to Computer Science! What are your thoughts? What have you tried? This kind of recurrence appears to be covered by our reference material, and in particular, the Akra-Bazzi method described there. I suggest that you work through the reference material, see if that meets your needs, and if it doesn't or if you are still stuck, edit to include your attempts along with the specific problems/issues you encountered. Your question can be considered for reopening at that point. $\endgroup$ – D.W. Feb 13 '17 at 5:11
0
$\begingroup$

You can find an upper bound like this: $T(n)\leq 3T(n/2)+n$.

Solving using master theorem, $T(n)=O(n^{log_23})$

$\endgroup$

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