📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    Question

    The recurrence relation T(n) = 2T(n/2) + O(n)

    corresponds to which algorithm’s time complexity?
    A Binary Search Correct Answer Incorrect Answer
    B Merge Sort Correct Answer Incorrect Answer
    C QuickSort worst-case Correct Answer Incorrect Answer
    D Insertion Sort Correct Answer Incorrect Answer
    E Heapify Correct Answer Incorrect Answer

    Solution

    Merge Sort divides in two (2T(n/2)) and merges in O(n), giving T(n)=O(n log n).

    Practice Next
    More Algorithms Questions
    ask-question