📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!
  • google app store apple app store
    • ✖

      Question

      Which sorting algorithm uses the 'Divide and Conquer'

      strategy and what is its recurrence relation?
      A Bubble Sort — T(n) = T(n−1) + O(n) Correct Answer Incorrect Answer
      B Insertion Sort — T(n) = T(n−1) + O(1) Correct Answer Incorrect Answer
      C Merge Sort — T(n) = 2T(n/2) + O(n), solving to O(n log n) Correct Answer Incorrect Answer
      D Selection Sort — T(n) = T(n−1) + O(n) Correct Answer Incorrect Answer
      E Counting Sort — T(n) = O(n+k) with no recurrence relation Correct Answer Incorrect Answer

      Solution

      Merge Sort applies Divide and Conquer in three phases: Divide: Split array into two halves recursively until subarrays of size 1 (base case — already sorted). Conquer: Recursively sort each half. Combine: Merge two sorted halves into one sorted array in O(n) time. Recurrence relation: T(n) = 2T(n/2) + O(n) — two recursive calls on n/2 elements each, plus O(n) merge step. Solved using Master Theorem (Case 2): T(n) = O(n log n).

      Practice Next
      More Algorithms Questions

      Relevant for Exams:

      ask-question