Question

Suppose that we performed the algorithm SELECT whose running time is O(n) on 133 elements, and found the median of medians x by making groups of 5 elements. What is the maximum number of elements which are guaranteed to be greater than equals to x (without counting x, itself)?

Answer 1

Let the 133 elements be 1,2,3,4,.....,100,....131,132,133

Making these 133 elements as groups of 5 elements. S0 1,2,3,4,5 are one group, 6,7,8,9,10 are one group.

Likewise the groups are:

11,12,13,14,15

16,17,18,19,20

.

.

.

.

96,97,98,99,100

.

.

.

.

126,127,128,129,130 and

131,132,133

Median: The elements should be in either ascending or descending order (ordered data).

1) If the number of observations(n) is odd then the median will be at position {(n + 1) ÷ 2}

2) If the number of observations(n) is even then

i. Find the value at position {n ÷ 2}

ii. Find the value at position {(n + 1) ÷ 2}

  iii. Find the average of these two values to get the median.

The median of the group elements 1,2,3,4,5 is 3

and

The median of the group elements 6,7,8,9,10 is 8

Therefore the medians of these groups are

3, 8, 13, 18, 23, 28, 33, 38, 43, 48, 53, 58, 63, 68, 73, 78, 83, 88, 93, 98, 103, 108, 113, 118, 123, 128, 132

There are 27(odd and ordered) medians. The median of medians will be at position {(n + 1) ÷ 2}

= {(n + 1) ÷ 2}

= {(27 + 1) ÷ 2}

= {28 ÷ 2}

= 14th position

= 68

Therefore the value of x = 68

The maximum number of elements which are guaranteed to be greater than equals to x (without counting x, itself) is 13 ( they are 73, 78, 83, 88, 93, 98, 103, 108, 113, 118, 123, 128, 132 without including x = 68)