Applying the Master Theorem to merge sort, T(n) = 2T(n/2) + n, the matching case and result are
Acase 1 (a < b^d), giving O(n)
Bcase 3 (a > b^d), giving O(n^log_2 2) = O(n)
Ccase 2 (a = b^d), giving O(n log n)
Dno case applies; use iteration
Answer & Solution
Correct answer: C. case 2 (a = b^d), giving O(n log n)
a = 2, b = 2, d = 1, so b^d = 2 = a. Case 2 applies. Result is O(n^d log n) = O(n log n). This matches the well-known merge sort running time without any unrolling or substitution; one of the cleanest applications of the master theorem.
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