Изменения

3. <tex>\log_b a > c </tex> <tex>\Rightarrow</tex> <tex dpi = "125"> T(n) = \displaystyle\sum_{i=1}^{\log_b n}n^c\cdot(\frac{a}{b^c})^i = n^c\cdot\displaystyle\sum_{i=1}^{\log_b n}(\frac{a}{b^c})^i = \Theta\left( n^c\cdot(\frac{a}{b^c})^{log_b n} \right)</tex>, но <tex dpi = "150"> n^c\cdot(\frac{a}{b^c})^{log_b n} </tex> <tex dpi = "130"> = </tex> <tex dpi = "150"> n^c\cdot(\frac{a^{log_b n} }{(b^c)^{log_b n}}) </tex> <tex dpi = "130"> = </tex> <tex dpi = "150"> n^c\cdot(\frac{n^{log_b a}}{n^c})</tex> <tex dpi = "130"> = </tex> <tex dpi = "130"> \Theta\left( n^{\log_b a} \right) </tex>

Пусть при решении поставленной задачи, существует алгоритм, который разбивает ее на <tex> a </tex> подзадач,при этом <tex>n</tex> — размер общей задачи, <tex dpi = "125">\dfrac{n}{b}</tex> — размер каждой подзадачи, <tex> n ^ {c} </tex> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач и <math>d</math> — начальная стоимость для данной задачи(при <tex>n = 1</tex>).Тогда мастер-теорема позволяет найти асимптотическое решение рекурренты, возникшей в результате анализа асимптотики данной задачи.

==Примеры==