CODEWITHSUNDEEP
algorithmmedian-of-medians
juimdpp
juimdpp

Reputation: 47

Dividing the list in 8 instead of 5 in the median of median algorithms

Image that explains the first algorithm

Generalized median-of-medians for sublist of size a

From this algorithm, we can see than in order to get linear running time for the algorithm, the constant has to be bigger than 4. However, I wondered what would happen if I divided into n/8 sublists and chose the 4th biggest number of each sublist as the median.

I expected the running time to be linear, since 8 > 4 however when I calculated the running time, I found O(nlogn). Calculating for sublist of size 8

Can someone please tell me if what I did is wrong, and explain to me why the sublist's size should always be odd?

Upvotes: 0

Views: 98

Answers (0)

Related Questions