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