Временная сложность алгоритма медианы медиан

Question

Здравствуйте, я беру Введение в класс алгоритмов этого семесетера.Однако у меня есть некоторая проблема в вычислении временной сложности алгоритма медианы медиан ( здесь ).Мне интересно, как получить T(n)<=10cn from T(n)<=T(0.2n)+T(0.7n)+cn..

Я думаю, что я не могу применить теорему о матере к приведенному выше выражению, и в Википедии сказано, что я должен использовать индукцию, но я не знаю, как ..

Answer 1

Используется индукция.Предположим, что меньше или равно n у нас есть T(n) <= 10*c*n (мы знаем, что основание индукции верно для равных или меньше T(10), поскольку они постоянны, и мы можем использовать достаточно большое значение для c).Теперь мы хотим доказать это для T(n + 1).Мы знаем T(n + 1) <= T(0.2(n + 1)) + T(0.7( n + 1)) + c(n+1).Из предположения индукции как 0.2(n + 1), так и 0.7(n+1) меньше, чем n (для n > 10), T(0.2(n + 1)) <= 10*c*0.2(n + 1) и T(0.7(n + 1)) <= 10*c*0.7(n + 1).Следовательно, T(n+1) <= 2*c(n+1) + 7*c(n+1) + n*c = 10*c*n.Доказательство завершено!