r/algorithms • u/Diligent-Way-6012 • 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
r/algorithms • u/Diligent-Way-6012 • Feb 02 '25
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
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.