1
$\begingroup$

What would be an efficient method to find the kth smallest element in an array with worst case time complexity being $ O(n) $?

$\endgroup$
1
$\begingroup$

You can use quickselect with median of medians to find a good pivot so that the total running time is linear in the worst case.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.