0% completed
Could you elaborate on why "return partition(medians, 0, len(medians)-1)" is don...
Mike Xu
Feb 19, 2023
Could you elaborate on why "return partition(medians, 0, len(medians)-1)" is done when getting the medianOfMedians? Isn't it sufficient to do "return medianOfMedians(medians)"? Since calling partition with anything will just end up calling medianOfMedians with the same thing until it hits the base case of n
0
0
Comments
Mike Xu3 years ago
I found that indeed we need the mutual recursion between medianOfMedians and partition in order to get the true median. Using a recursion of medianOfMedians will only give us an approximate median which is quite far off from the real median sometimes. More details here:...
Mike Xu3 years ago
The above is right in that we cannot only have medianOfMedians recursively call itself. But it is not correct to have medianOfMedians and partition be mutually recursive, please see my newest comment for the correct approach.
Having medianOfMedians recursively call its...
On this page