3622
правки
Изменения
м
→Формулировка и доказательство мастер-теоремы
мастер-теорема
|statement=
Пусть имеется рекуррентное соотношения вида:
<tex dpi = "135"> T(n) = \begin{cases}
где <tex>a</tex> <tex>\in \mathbb N </tex>, <tex>b</tex> <tex> \in \mathbb R </tex>, <tex> b > 1</tex>, <tex>c</tex> <tex>\mathbb \in R^{+} </tex>.
Тогда асимптотическим решением данного соотношения будет один из трёх случаев нижеасимптотическое решение имеет вид:
# Если <tex>c > \log_b a</tex>, то <tex>T(n) = O\left( n^{c} \right)</tex>
