Which recurrence is characteristic of an algorithm that divides a problem into two equal subproblems and performs linear work to combine their results?

Options

  • A. T(N) = 2T(N/2) + O(N)
  • B. T(N) = T(N - 1) + O(1)
  • 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)

A. T(N) = 2T(N/2) + O(N)

Detailed Explanation

A recurrence of the form T(N) = 2T(N/2) + O(N) describes an algorithm that creates two subproblems of approximately half the original size and performs linear work outside the recursive calls. Merge Sort is the standard example. Using the Master Theorem, this recurrence evaluates to O(N log N). Recognizing recurrence patterns is important for analyzing Divide and Conquer algorithms in DSA.

← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts