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) $?

| cite | improve this question | | | | |
$\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.