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$

marked as duplicate by xskxzr, Community Apr 30 at 11:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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.

$\endgroup$

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