Изменения

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

<tex> t(xn) = \begin{cases} 2 \; t\!\left(\dfrac{xn}{2}\right) + O(n\log n) , & n > 1\\

Заметим, что <tex> n\log n = O(n^c) </tex>, для любого <tex> c > 1 </tex>, что удовлетворяет 1 условию. Тогда <tex> T(n) = O(n^c) </tex>, где <tex> c > 1 </tex>, при <tex> a = 2, b = 2, \log_b a = 1</tex>

*:<tex>a</tex> не является константой; количество подзадач может меняться,*<tex dpi = "130">T(n) = 2T\left (\dfrac{n}{2}\right )+O\left(\fracdfrac{n}{\log n}\right)</tex>*:рассмотрим <tex> f(n) = \dfrac{n}{\log n} </tex> , тогда не существует такого <tex> O(n^c) </tex>, что <tex> f(n) \in O(n^c) </tex> , т.к. так как при <tex> n = 1 , f(n) \rightarrow \!\, \infty </tex>, а <tex> O(n^c) </tex> ограничено.,

*:<tex>|a | < 1</tex> не может быть меньше одной подзадачи. Однако , однако пример можно решить следующим образом: заметим, что на <tex> i </tex> шаге, размер <tex> T(i) \leqslant \dfrac{c \cdot n}{4^i} </tex> , тогда, оценивая сумму, получаем, что <tex> T(n) = O(n) </tex>.,