title: Median of Medians
body: <p>I have read the order statistics to find the k-th smallest (or largest) element in an array of size n in linear time O(n).</p>
  
  <p>There is one step that it needs to find the median of the medians.</p>
  
  <ol>
  <li>Split the array into [n/5] parts. Each part has 5 elements.</li>
  <li>Find the median in each part. (We have [n/5] numbers now)</li>
  <li>Repeat step 1 and 2 until we only have the last number. (i.e. recursive)</li>
  </ol>
  
  <p>T(n) = T(n/5) + O(n)
  and we can get T(n) = O(n).</p>
  
  <p>But, is it true that, the number we finally get is not the median of medians, but the median of medians of medians of medians of medians of medians, if we have a large array.</p>
  
  <p>Please consider an array which has 125 elements.</p>
  
  <p>First, it is split into 25 parts and we find 25 medians.
  Then, we split these 25 numbers into 5 parts and find 5 medians,
  Finally, we obtain the number which is median of medians of medians. (Not median of medians)</p>
  
  <p>The reason why I care about it is that, I can understand there are at most about [3/4]*n elements that are smaller (or larger) than the median of medians. But what if it is not the median of medians but the median of medians of medians? In worse case there must be less elements that are smaller (or larger) than the pivot, which means the pivot is closer to the bound of the array.</p>
  
  <p>If we have a VERY large array, and we found its median of medians of medians of medians of medians of medians. In the worst case the pivot we found can still be very close to the bound and what is the time complexity in this case?</p>
  
  <p>I made up a dataset of 125 elements. Is the result 9?</p>
  
  <pre><code>0.8 0.9 1 inf inf
  1.8 1.9 2 inf inf
  6.8 6.9 7 inf inf
  inf inf inf inf inf
  inf inf inf inf inf
  
  2.8 2.9 3 inf inf
  3.8 3.9 4 inf inf
  7.8 7.9 8 inf inf
  inf inf inf inf inf
  inf inf inf inf inf
  
  4.8 4.9 5 inf inf
  5.8 5.9 6 inf inf
  8.8 8.9 9 inf inf
  inf inf inf inf inf
  inf inf inf inf inf
  
  inf inf inf inf inf
  inf inf inf inf inf
  inf inf inf inf inf
  inf inf inf inf inf
  inf inf inf inf inf
  
  inf inf inf inf inf
  inf inf inf inf inf
  inf inf inf inf inf
  inf inf inf inf inf
  inf inf inf inf inf
  </code></pre>
  
  <p>where inf means the number is large enough.</p>