Учитывая массив A с n элементами (скажем, целыми числами), я хотел бы знать сложность времени для алгоритма сортировки O(nlog(n)), когда я использую его для сортировки ТОЛЬКО подмассива-
A[floor(n/2)+1], A[floor(n/2)+2], ... , A[floor(n/2)+n/log(n)] - Всего n/log(n) элементов.
Я пытался установить n = n/log(n) в n*log(n), таким образом -
(n/log(n)) * (log(n/log(n))) =
(n/log(n)) * (log(n)-log(log(n))) =
(n*log(n) - n*log(log(n))) / (log(n))
Я застрял здесь, кто-нибудь может помочь? Спасибо.