# How do you solve a recurrence relation with multiple subproblems of different sizes? [duplicate]

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?

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

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})$