Изменения
Нет описания правки
5.Если <tex>i</tex> <tex>=</tex> <tex>k</tex>, то возвращается значение <tex>x</tex>. Иначе вызывается рекурсивно шаг 1, и выполняется поиск <tex>k</tex>-го в порядке возрастания элемента в левой части массива,если <tex>i</tex> <tex><</tex> <tex>k</tex>, или в правой части, если <tex>i</tex> <tex>></tex> <tex>k</tex>.
===Особенность алгоритма===
Как будет доказано ниже, время работы алгоритма в наихудшем случае равно <tex>O(n)</tex>. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива, так как чисел, которые меньше рассекающего элемента не менее <tex>\frac{3n}{10}</tex>, где <tex>n</tex> количество элементов в массиве.
== Анализ времени работы алгоритма ==
Пусть <tex>T(n)</tex> - время работы алгоритма для <tex>n</tex> элементов, тогда оно не больше, чем сумма:
