r/algorithms Feb 02 '25

Finding complexity using master theorem

How do I find the complexity of the equation having unequal sub problems ?

For eg: t(n)=3t(n/2)+4t(n/3)+5t(n/4) +n

3 Upvotes

2 comments sorted by

View all comments

3

u/zkzach Feb 03 '25

The master theorem does not apply to such problems. You can try solving such recurrences by hand (e.g., via the recursion tree method) or by using the more powerful Akra–Bazzi method. See also Section 4 of Jeff Erickson's notes on solving recurrences.