We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Agreed! The average-case solution for QuickSelect is indeed O(n). Unfortunately, when the list is sorted (or "nearly" sorted), your algorithm will degenerate to the worst-case of O(n*n)... :(

Hi. I agree, O(n^2) can happen, but this worst-case O(n^2) happens extremely rarely. It's O(n) 99.99%+ of the time for randomly generated data. To get the degenerate case, the user would have to provide data in a specific way to break quickselect based on how the pivot is selected. Such cases are mostly a concern if a hacker is intentionally trying to break quickselect.

Quickselect doesn't become O(n^2) just because the data is sorted. 3 things have to align for the runtime to reach O(n^2), for sorted data, here are the 3 things (from Wikipedia)
1) Data is sorted
2) User is searching for the maximum element in a set (which is usually not the case, since a sorting algorithm is not a good way to find the max element)
3) The first element is used as a pivot

If you look into how I implemented QuickSelect you will see that I do not choose the starting element as a pivot, so my code will still run in O(n) on a sorted list.

As a personal preference, I'm happy getting O(n) 99% of the time with the rare case of O(n^2).

Agreed! For a high-volume website, however, we cannot bet on the worst-case of O(n*n) even if it has a mere chance of 0.01%, especially when millions of searches are conducted per day. FYI, 1 million multiplied by 0.01% = 100.

## Luck Balance

You are viewing a single comment's thread. Return to all comments →

## Java O(n) solution

Using QuickSelect, you can get an O(n) average-case solution.

The full solution is in my HackerRank solutions. Here is a snippet of the code.

Let me know if you have any questions.

Agreed! The average-case solution for QuickSelect is indeed O(n). Unfortunately, when the list is sorted (or "nearly" sorted), your algorithm will degenerate to the worst-case of O(n*n)... :(

Hi. I agree, O(n^2) can happen, but this worst-case O(n^2) happens

extremelyrarely. It's O(n) 99.99%+ of the time for randomly generated data. To get the degenerate case, the user would have to provide data in a specific way to break quickselect based on how the pivot is selected. Such cases are mostly a concern if a hacker is intentionally trying to break quickselect.Quickselect doesn't become O(n^2) just because the data is sorted. 3 things have to align for the runtime to reach O(n^2), for sorted data, here are the 3 things (from Wikipedia)

1) Data is sorted

2) User is searching for the maximum element in a set (which is usually not the case, since a sorting algorithm is not a good way to find the max element)

3) The first element is used as a pivot

If you look into how I implemented QuickSelect you will see that I do not choose the starting element as a pivot, so my code will still run in O(n) on a sorted list.

As a personal preference, I'm happy getting O(n) 99% of the time with the rare case of O(n^2).

Cheers!

Agreed! For a high-volume website, however, we cannot bet on the worst-case of O(n*n) even if it has a mere chance of 0.01%, especially when millions of searches are conducted per day. FYI, 1 million multiplied by 0.01% = 100.

A good implementation of the algorithm will have randomization built in, such that the order of the list does not matter.

Agreed! On the other hand, even with randomization builtin, QuickSelect still has the worst-case of O(n*n), however improbable it may be.