Изменения
Нет описания правки
T(n) = 2T(n/2) + O(n) = 4T(n/4) + 2*O(n) = ... = 2^kT(1) + kO(n).
Осталось оценить <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(nlogn\log(n))</tex>.
=Ссылки=
*[http://ru.wikipedia.org/wiki/Mergesort| Википедия - сортировка слиянием]
*[http://iproc.ru/parallel-programming/lection-6/| Сортировка слиянием]
