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.
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).
Luck Balance
You are viewing a single comment's thread. Return to all comments →
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).
Cheers!