Which recurrence relation represents the standard Merge Sort algorithm?

Options

  • 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. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

B. T(n) = 2T(n/2) + O(n)

Detailed Explanation

The standard recurrence for Merge Sort is T(n) = 2T(n/2) + O(n). The term 2T(n/2) represents recursively sorting two halves of the input, while O(n) represents merging the two sorted halves. Using the Master Theorem, this recurrence gives O(n log n). Understanding this recurrence is useful for recognizing Divide and Conquer algorithms and calculating their time complexity.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts