k-th Smallest Number In List

One way to find to find the \(k\)th smallest element in a list is to first sort the list, and then take the \(k\)th element in the sorted list.

However, sorting has a minimum worst-case runtime of \(O(n\log(n)).\) Is it possible to find the \(k\)th smallest element with worst-case runtime \(O(n)?\)

Bonus: Prove your answer!

×

Problem Loading...

Note Loading...

Set Loading...