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>a, b, c</tex> такбудет один из трёх случаев ниже:
# Если <tex>c > \log_b a</tex>, то <tex>T(n) = O\left( n^{c} \right)</tex>
