Изменения

a \; T\!\left(\dfrac{n}{b}\right) + O(n^{c} ) , & n > 1\\ d O(1) , & n = 1

где <tex>a</tex> — <tex>\in \mathbb N </tex> число большее ,и <tex>a \ne 1</tex>, <tex>b</tex> — <tex>\in \mathbb R </tex> число большее , и <tex> b >1</tex>, <tex>c</tex> — <tex>\mathbb \in R^{+} </tex> число и <tex>d</tex> — <tex>\in \mathbb R^{+} </tex>.

|proof= Давайте рассмотрим Заметим, что <tex> O(1) </tex> не влияет на дальнейшее рассмотрение, т.к. оно учитывается не более чем константное число раз, что не существенно в асимптотике алгоритма. Рассмотрим дерево рекурсии. Всего в нем будет <tex>\log_b n</tex> уровней. На каждом таком уровне, количество подзадач будет умножаться на <tex>a</tex>, так на уровне <tex>i</tex> будет <tex>a^i</tex> подзадач. Также известно, что каждая подзадача на уровне <tex>i</tex> размера <tex>O\left(\dfrac{n}{b^i}\right)</tex>. Подзадача размера <tex>O\left(\left(\dfrac{n}{b^i}\right)\right)</tex> требует <tex>O\left(\left(\dfrac{n}{b^i}\right) ^ c\right)</tex> дополнительных затрат, поэтому общее количество совершенных операций на уровне <tex>i</tex> : <tex>O\left(a^i\left(\dfrac{n}{b^i}\right)^c \right) = O\left(n^c\left(\dfrac{a^i}{b^{ic}}\right)\right) = O\left(n^c\left(\dfrac{a}{b^c}\right)^i\right)</tex>

 Поэтому мы должны разобрать три случая, когда <tex>\left(\dfrac{a}{b^c}\right)^i</tex> больше <tex>1</tex>, равен <math>1</math> или меньше <math>1</math>. Рассмотрим <tex dpi = "140130">\left(\dfrac{a}{b^c}\right)^i = 1</tex> <tex dpi = "140">\Leftrightarrow a = b^c\Leftrightarrow\ \ log_b a = c \log_b b\Leftrightarrow\ \log_b a = c</tex>. 

<tex dpi = "130"> d\cdot \displaystyle\sum_{i=1}^{\log_b n}n^c\left(\frac{a}{b^c}\right)^i = O\left(n^c\cdot d \cdot\displaystyle\sum_{i=1}^{\log_b n}\left(\frac{a}{b^c}\right)^i\right)</tex>

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

3 \; t\!\left(\dfrac{x}{2}\right) + x^n\sqrt{2n + 1} , & x \ge 2n > 1\\ 5x 1 , & n = 1 \le x < 2

Заметим, чтобы узнать Рассмотрим <tex>tf(7n)</tex> , мы должны знать <tex>t\left(= n\dfracsqrt{7}{2n+1}= \right)</tex>, чтобы узнать <tex>t\leftTheta(\dfrac{7}n^{3/2}\right)</tex>, мы должны узнать тогда данное соотношение удовлетворяет случаю <tex>tc < \left(\dfrac{7}{4}\right)log_b a</tex>, а именно <tex>1 < \dfrac{73}{4} < 2</tex>, тогда <tex>t\left(\dfrac{7}{4}\right) = \dfrac{35}{4}</tex> , <tex>t\left(\dfrac{7}{2}\right) = log_2 3\cdot\dfrac{35}{4} + \dfrac{49}{4}</tex>, тогда асимптотикой является <tex>t(7) = 3t\leftTheta(n ^ {\dfrac{7}{2log_2 3}\right) + 7^2 = \dfrac{329}{2}</tex>.

*:не удовлетворяет условию рассмотрим <tex> f(n) = \dfrac{n}{\log n} </tex> , тогда не равно существует такого полинома, что <tex> \dfrac{n}{\log n} \in \Theta(n^c ) </tex>

*:<tex>a< 1</tex> < 1 не может быть меньше одной подзадачи