Изменения

<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>