The average-case time complexity of the Quickselect algorithm, used to find the k-th smallest element of an unsorted array of n elements, is

Explanation

Quickselect partitions the array like quicksort but continues in only one part, so the expected work is n + n/2 + n/4 + … = O(n), although the worst case is O(n²).