alleryStart learning →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.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.