Изменения

# времени работы для поиска <tex>k</tex>-го элемента в одной из двух частей массива, то есть <tex>T(s)</tex>, где <tex>s</tex> — количество элементов в этой части. Но <tex>s</tex> не превосходит <tex dpi = "170">\frac{7n}{10}</tex>, так как чисел, меньших рассекающего элемента, не менее <tex dpi = "170">\frac{3n}{10}</tex> — это <tex dpi = "170">\frac{n}{10}</tex> медиан, меньших медианы медиан, плюс не менее <tex dpi = "170">\frac{2n}{10}</tex> элементов, меньших этих медиан. С другой стороны, чисел, больших рассекающего элемента, так же не менее <tex dpi = "170">\frac{3n}{10}</tex>, следовательно <tex> s \le leqslant </tex> <tex dpi = "170">\frac{7n}{10}</tex>, то есть в худшем случае <tex> s = </tex> <tex dpi = "170">\frac{7n}{10}</tex>.

<tex>T(n) \le leqslant T(</tex><tex dpi = "170">\frac{n}{5}</tex><tex>) + T(</tex><tex dpi = "170">\frac{7n}{10}</tex><tex>) + Cn </tex>

Покажем, что для всех <tex> n </tex> выполняется неравенство <tex>T(n) \le leqslant 10Cn </tex>.

# Предположим, что наше неравенство <tex>T(n) \le leqslant 10Cn </tex> выполняется при малых <tex> n </tex>, для некоторой достаточно большой константы <tex> C </tex>. # Тогда, по предположению индукции, <tex>T(</tex><tex dpi = "170">\frac{n}{5}</tex><tex>) \le leqslant 10C </tex><tex dpi = "170">\frac{n}{5}</tex><tex> = 2Cn</tex> и <tex> T(</tex><tex dpi = "170">\frac{7n}{10}</tex><tex>) \le leqslant 10C </tex><tex dpi = "170">\frac{7n}{10}</tex><tex> = 7Cn</tex>, тогда<tex>T(n) \le leqslant T(</tex><tex dpi = "170">\frac{n}{5}</tex><tex>) + T(</tex><tex dpi = "170">\frac{7n}{10}</tex><tex>) + Cn = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \le leqslant 10Cn</tex>

Так как <tex>T(n) \le leqslant 10Cn </tex>, то время работы алгоритма <tex>O(n)</tex>