ЁЯУв Too many exams? DonтАЩt know which one suits you best? Book Your Free Expert ЁЯСЙ call Now!

    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
    More Algorithms Questions
    ask-question