Hello I am trying to understand how the median of medians algorithm works. In all examples I've seen so far there already are the groups of the numbers divided , before the execution of the algorithm begins. So I cannot understand how these groups are made. To be more specific at the examples studied so far, is stated that there are 9 groups of 5 numbers each, for example aka 45 numbers, or 4 groups of 10 numbers aka 40 numbers at all. So what if we have n numbers..? Is there any good technique that should I follow to find the number of elements its group should have ?
1
There are 1 best solutions below
Related Questions in ALGORITHM
- Add image to JCheckBoxMenuItem
- How to access invisible Unordered List element with Selenium WebDriver using Java
- Inheritance in Java, apparent type vs actual type
- Java catch the ball Game
- Access objects variable & method by name
- GridBagLayout is displaying JTextField and JTextArea as short, vertical lines
- Perform a task each interval
- Compound classes stored in an array are not accessible in selenium java
- How to avoid concurrent access to a resource?
- Why does processing goes slower on implementing try catch block in java?
Related Questions in MEDIAN-OF-MEDIANS
- Add image to JCheckBoxMenuItem
- How to access invisible Unordered List element with Selenium WebDriver using Java
- Inheritance in Java, apparent type vs actual type
- Java catch the ball Game
- Access objects variable & method by name
- GridBagLayout is displaying JTextField and JTextArea as short, vertical lines
- Perform a task each interval
- Compound classes stored in an array are not accessible in selenium java
- How to avoid concurrent access to a resource?
- Why does processing goes slower on implementing try catch block in java?
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
MoM is a recursive algorithm. It exists as a sound way to select a "pivot" for an algorithm like quicksort or quickselect. Thus, it needs to operate within certain time bounds.
It might be easier to understand if explained as a base case and a recursive case.
The base case is clear enough. If you have less than five elements in a list, then you find the median the naive way.
But, if your list has at least five elements, you can apply the recursive case. You're going to take successive groups of five elements from your big list, find their median, and add it to a smaller list. (If you have some left over, you can ignore them.)
If this new, smaller list is small enough, you can apply the base case, as described above. Otherwise, you'll go through the "small" list to create another, still smaller list. Lather, rinse, and repeat until you get down to less than five elements remaining. And that's your estimate of the overall median. So it works with any size of list.
So how big should "five" be? Well, it turns out that 5 is optimal. Someone showed the complexity analysis over at the Wikipedia page for this topic. Essentially, larger values of "five" get you a better approximation of the median at the cost of more work to find the median of "five". Unfortunately 3 does not decrease the search space enough per iteration to be a worthwhile choice of "five". And it generally needs to be odd, unless you want to spend cycles splitting the difference between elements.