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