Understanding “median of medians” algorithm

by

The problem is in the step where you say to find the true median of the medians. In your example, you had these medians:

50 45 40 35 30 25 20 15 10

The true median of this data set is 30, not 15. You don’t find this median by splitting the groups into blocks of five and taking the median of those medians, but instead by recursively calling the selection algorithm on this smaller group. The error in your logic is assuming that median of this group is found by splitting the above sequence into two blocks

50 45 40 35 30

and

25 20 15 10

then finding the median of each block. Instead, the median-of-medians algorithm will recursively call itself on the complete data set 50 45 40 35 30 25 20 15 10. Internally, this will split the group into blocks of five and sort them, etc., but it does so to determine the partition point for the partitioning step, and it’s in this partitioning step that the recursive call will find the true median of the medians, which in this case will be 30. If you use 30 as the median as the partitioning step in the original algorithm, you do indeed get a very good split as required.

Hope this helps!

More Related Contents:

  1. Find the k largest elements in order
  2. O(n) or O(n)^2 time complexity of the algorithm? [closed]
  3. How can I find the time complexity of an algorithm?
  4. Finding all cycles in a directed graph
  5. Peak signal detection in realtime timeseries data
  6. How to compare two colors for similarity/difference
  7. Least common multiple for 3 or more numbers
  8. What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?
  9. Negative weights using Dijkstra’s Algorithm
  10. What’s the fastest algorithm for sorting a linked list?
  11. Need help in mod 1000000007 questions
  12. SICP example: Counting change, cannot understand
  13. Check if one integer is an integer power of another
  14. Quicksort: Iterative or Recursive
  15. How best to sum up lots of floating point numbers?
  16. Algorithm to tell if two arrays have identical members
  17. Quicksort vs heapsort
  18. Find 2 numbers in an unsorted array equal to a given sum
  19. finding a^b^c^… mod m
  20. Algorithm to find the most common substrings in a string
  21. Simplest way to get the top n elements of a Scala Iterable
  22. Find cycle of shortest length in a directed graph with positive weights
  23. Random points inside a parallelogram
  24. How is 2D bin packing achieved programmatically?
  25. Optimizing Conway’s ‘Game of Life’
  26. What are the pitfalls in implementing binary search? [closed]
  27. Best way to find a point on a circle closest to a given point
  28. Can a Fibonacci function be written to execute in O(1) time?
  29. What Are High-Pass and Low-Pass Filters?
  30. Given a set of intervals, find the interval which has the maximum number of intersections

Leave a Comment