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.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for