Running time of Algo

Правка en2, от gXa, 2016-01-10 15:25:53

We have designed an new algorithm to sort a list of n numbers. We recursively partition the numbers into groups of size sqrt(n) each until we are left with lists of constant size; at which point we use insertion sort to sort the numbers. To combine solutions, we do a merge of the sorted lists, namely maintaining pointers to the start of the list and at each step advancing the pointer of the list corresponding to the smallest element. Let T(n) denote the running time of this algorithm (we can assume that sqrt(k) is an integer for all k<=n encountered in the algorithm).

Running time : T(n) <= sqrt(n) T( sqrt(n) ) + O(n^1.5)

I can think of it as T(n) = T( sqrt(n) ) + T( n-sqrt(n) ) + O(n) but can't relate to the solution. Plz can anybody explain its running time.

Теги sort

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский gXa 2016-01-10 15:25:53 26
en1 Английский gXa 2016-01-10 15:14:05 800 Initial revision (published)