Почему алгоритм медианы медианы не может использовать размер блока 3 ?

Я работаю над анализом детерминированного определения медианы в предположении, что входные данные делятся на 3 части, а не на 5, и вопрос в том, где они ломаются?

детерминированный алгоритм поиска медианы:

SELECT (i, n)

1. Разделите n элементов на группы по 5. Найдите наизусть медианное значение каждой группы из 5 элементов.

2. Рекурсивно ВЫБРАТЬ медиану x для ⎣n / 5⎦ групповые медианы в качестве точки поворота.

3. Разделение вокруг оси x. Пусть k = rank (x)

4.если i = k, то вернуть x

иначе, если i

, то рекурсивно ВЫБРАТЬ i-й наименьший элемент в нижней части

иначе рекурсивно ВЫБЕРИТЕ (i – k) -й наименьший элемент в верхней части

Я провел анализ алгоритма и считаю, что на этапах 1 и 3 потребуется O (n), где требуется только постоянное время, чтобы найти медиану из 5 элементов, а на этапе 2 требуется T ( n / 5), поэтому по крайней мере 3/10 элементов имеют ≤ p, и по крайней мере 3/10 массива ≥ p, поэтому на шаге 4 будет T (7n / 10) и будет повторяться. Т (п) ≤ сп + Т (п / 5) + Т (7n / 10), но когда я делю элементы на группу из 3, скажем, 9 элементов, и я разделил их на группы так, чтобы:

{1,2,10} {4,11,14}, {15,20,22}

Я получил медианы 2,11,20 и p = 11.

в целом в группе из пяти человек допустим, что g = n / 5 групп и не менее ⌈g / 2⌉ из них (те группы, у которых медиана ≤ p) по крайней мере три из пяти элементов ≤ p. поэтому общее количество элементов ≤ p не менее 3⌈g / 2⌉ ≥ 3n / 10. НО в группе из 3 элементов мы можем получить все три элемента МЕНЬШЕ, чем p. и вот думаю алгоритм сломается !!

Я правильно понял ???