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

    Question

    What is the worst-case time complexity of QuickSort with

    a random pivot for sorting n distinct elements?
    A O(n log n) expected, O(n²) worst-case Correct Answer Incorrect Answer
    B O(n²) expected, O(n log n) worst-case Correct Answer Incorrect Answer
    C O(n) expected, O(n log n) worst-case Correct Answer Incorrect Answer
    D Always O(n log n) worst-case Correct Answer Incorrect Answer
    E O(nÂł) worst-case Correct Answer Incorrect Answer

    Solution

    Randomized quicksort has expected O(n log n) but rare worst-case O(n²) if partitions are very unbalanced (though random pivot makes worst-case improbable).

    Practice Next
    More Algorithms Questions
    ask-question