alleryStart learning →Which recurrence is the Master Theorem (as stated) NOT able to solve?
AT(n) = 4T(n/2) + Θ(n²)
BT(n) = 3T(n/2) + Θ(n)
CT(n) = T(n/2) + Θ(1)
DT(n) = T(n/3) + T(2n/3) + n
Answer & Solution
Correct answer: D. T(n) = T(n/3) + T(2n/3) + n
Master Theorem (in its standard form) requires that the sub-problems all have the same size n/b for some integer b > 1. T(n/3) + T(2n/3) splits into two sub-problems of DIFFERENT sizes (n/3 and 2n/3)
so the theorem doesn't apply.
The Akra-Bazzi generalisation handles this case.
The other three recurrences all fit standard master form.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.