Изменения

1. <math>\log_b a < c \log_b b</math> <math>\Rightarrow</math> <math>T(n) = \Theta\left( n^{c} \right)</math> (т.к. <tex dpi = "130"> (\frac{a}{b^c})^i</tex> убывающая геометрическая прогрессия)

2. <math>\log_b a = c \log_b b</math> <math>\Rightarrow</math> <tex dpi = "130"> T(n) = \displaystyle\sum_{i=1}^{log_b n}n^c(\frac{a}{b^c})^i = n^c\displaystyle\sum_{i=1}^{log_b n}(\frac{a}{b^c})^i = n^c\displaystyle\sum_{i=1}^{log_b n}1^i = n^c + n^c\log_b n\ = \Theta\left( n^{c} \log n \right) </tex>

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