Изменения

Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=log(n)</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ log(n)O(n)</tex>. Так как <tex>T(1)</tex> - константа, то <tex>T(n)=O(n)+log(n)O(n)=O(nlog(n))</tex>.