Difference between revisions of "Talk:TADM2E 4.1"
From Algorithm Wiki
Landisdesign (talk | contribs) m |
|||
| Line 1: | Line 1: | ||
| − | I'm confused. How do you find the median in O(n)? I can see finding the mean, but not the median. | + | == I'm confused. How do you find the median in O(n)? I can see finding the mean, but not the median. == |
| + | |||
| + | |||
| + | A possible answer for this question may be to use quickselect that can be seen as a partial quicksort where you only partition the side that will interest you until you get the pivot at the right position which is here n/2 . quickselect is known to have an expected time of O(n) and do the partition work as well. | ||
| + | |||
| + | Another deterministic method whose worst case is O(n) exists to find the median. So you could use it to find the median first and then use this median as pivot as proposed in the solution. | ||
Latest revision as of 12:32, 2 July 2020
I'm confused. How do you find the median in O(n)? I can see finding the mean, but not the median.
A possible answer for this question may be to use quickselect that can be seen as a partial quicksort where you only partition the side that will interest you until you get the pivot at the right position which is here n/2 . quickselect is known to have an expected time of O(n) and do the partition work as well.
Another deterministic method whose worst case is O(n) exists to find the median. So you could use it to find the median first and then use this median as pivot as proposed in the solution.
