What is the recurrence relation for Merge Sort?

A. T(n) = T(n-1) + O(1)
B. T(n) = 2T(n/2) + O(n)
C. T(n) = T(n/2) + O(1)
D. T(n) = T(n/2) + O(n)

Explanation:

Merge Sort divides the array in half and merges, giving T(n) = 2T(n/2) + O(n).

Tags: Algorithms MCQ , Computer Science