CS4GATE

Algorithms / Sorting

The average-case time complexity of Quick Sort is?

MCQ 2022 Quick Sort

The average-case time complexity of Quick Sort is?

Choose an Option

Answer

O(n log n)

Theory

Quick Sort uses divide-and-conquer with recurrence T(n) = 2T(n/2) + O(n) on average.

Solution

Solving the recurrence gives O(n log n).

Open Interactive Question All Questions

Previous QuestionWhich of the following are valid collision resolution techniques?Data Structures / Collision Handling Next QuestionMerge Sort's worst-case space complexity is?Algorithms / Merge Sort

Practice More From This Topic

Merge Sort's worst-case space complexity is?Algorithms / Merge Sort / 2023

More Algorithms Questions

Merge Sort's worst-case space complexity is?Algorithms / Merge Sort / 2023 Dijkstra's algorithm fails when the graph has?Algorithms / Dijkstra's Algorithm / 2023 Time complexity of 0/1 Knapsack via DP with n items and capacity W?Algorithms / 0/1 Knapsack / 2024 Given activities with start/end times, the greedy strategy that maximizes the number of activities selects activities sorted by which attribute? (1 = start time, 2 = end time)Algorithms / Activity Selection / 2022

Keep practicing

Want filters, bookmarks, progress, quiz, and mock tests?

Read questions freely here, or sign in to continue with dashboard practice and paid test tools.

Start Free View Paid Plan