New Click here to Enroll for SIDBI MSME Expert Class by ex-GM, SBI on Nov 24

    Register

    Question

    Which of the following is true about the time complexity of Merge Sort?

    A Best case: O(n), Worst case: O(n^2) Correct Answer Incorrect Answer
    B Best case: O(log n), Worst case: O(log n) Correct Answer Incorrect Answer
    C Best case: O(n log n), Worst case: O(n log n) Correct Answer Incorrect Answer
    D Best case: O(n), Worst case: O(n log n) Correct Answer Incorrect Answer
    E Best case: O(n^2), Worst case: O(n^2) Correct Answer Incorrect Answer

    Solution

    Correct Option: Merge Sort (C) has a time complexity of O(n log n) in both the best and worst cases due to its divide-and-conquer approach, where the list is recursively split and merged. Why Other Options Are Wrong: A) O(n), O(n^2): Merge Sort does not have a quadratic time complexity in the worst case, nor does it achieve linear time in the best case. B) O(log n), O(log n): This is incorrect as merge sort deals with linear elements and requires O(n log n) time due to both sorting and merging. D) O(n), O(n log n): While some algorithms achieve linear time in the best case, Merge Sort consistently performs at O(n log n). E) O(n^2), O(n^2): This complexity is associated with algorithms like bubble sort in the worst case, not Merge Sort.

    Practice Next