Per the Master Theorem, the three cases for T(n) = a · T(n/b) + c n^d are decided by comparing
Aa + b vs d
Ba vs b^d
Cn vs b^d
Da · b vs d
Answer & Solution
Correct answer: B. a vs b^d
Master theorem compares a (sub-problem count) to b^d (per-level divide-work growth) to decide which level dominates. a < b^d: top dominates, O(n^d). a = b^d: all levels equal, O(n^d log n). a > b^d: bottom dominates, O(n^log_b a). The other expressions are nonsense for this purpose.
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