algorithmsortingmedianmedian-of-medians

Finding block median in median of medians algorithm

I know that formula for the median of medians algorithm is : T(n)<= T(0.7n)+T(0.2n)+O(n) and O(n) came from finding median of each block(size of 5), and I'm wondering why It takes O(n) to find median of each block.. that sound like finding median of one block takes O(1). How is it possible?

Solution

  • Size of each block is constant (5). Hence, Finding the median of each block is in O(1) (sort the block in O(1) and take the mid index as a median). Therefore, finding the median of all blocks is in O(n). And after that find the median of the median of each block which is answered in your other question.