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.
Quickselect has worst-case time complexity O(n2) same as quicksort, but practical complexity O(n).
The problem should have explained that. From the definition it's unclear what we were supposed to do. Easiest approach is to just sort the array and get the middle element. Unless you know math, it's unclear why selection is supposed to have better complexity than sort, because from simply eyeballing it it looks exactly the same.
Find the Median
You are viewing a single comment's thread. Return to all comments →
The problem wants to demonstrate "selection algorithm". Specifically the implementation is Quickselect.
https://en.wikipedia.org/wiki/Selection_algorithm
https://en.wikipedia.org/wiki/Quickselect
Quickselect has worst-case time complexity O(n2) same as quicksort, but practical complexity O(n).
The problem should have explained that. From the definition it's unclear what we were supposed to do. Easiest approach is to just sort the array and get the middle element. Unless you know math, it's unclear why selection is supposed to have better complexity than sort, because from simply eyeballing it it looks exactly the same.