Algorithms and Data Structures · Senior · Question 16 of 75
What is the average complexity of quickselect for finding the k-th smallest element?
- 1O(log n)
- 2O(n log n)
- ✓Correct answer: O(n)
Explanation
Like quicksort it partitions, but it recurses only into the side that contains position k, so the work is n + n/2 + n/4 + ... ≈ 2n. The worst case is O(n²); median of medians guarantees O(n) with a bigger constant.