Geek Answers Handbook

Prove that optimized merge runtime is theta (NK + Nlog (N / K))?

Well, I know that Mergesort has the worst theta time (NlogN), but its overhead is high and appears near the bottom of the recursion tree where the merges are done. Someone suggested stopping the recursion after the size reaches K and switching to sorting at that point. Do I need to prove that the running time of this modified recursive relation is theta (NK + Nlog (N / k))? I am not talking about how to approach this problem.

+5
source share
1 answer

Perhaps a good start is to look at the recurrence ratio for this problem. I assume that for a typical mergesort it will look something like this:

T(N) = 2 * T(N / 2) + N

i.e. you divide the problem into 2 subtasks equal to half the size, and then do the N-job (merge). We have a base case that takes constant time.

Modeling this as a tree, we have:

T(N)   =   N   ->   T(N / 2)   
               ->   T(N / 2)

       =   N   ->   (N / 2)   ->   T(N / 4)
                              ->   T(N / 4)
               ->   (N / 2)   ->   T(N / 4)
                              ->   T(N / 4)

It gives decomposition

T(N) = N + 2N/2 + 4N/4 + ...
     = N + N + N ...

So we really need to see how deep this is happening. We know that the inth level works by subtask N / 2^iby size. Therefore, our leaf nodes ( T(1)) are found at a level Lwhere N / 2^L = 1:

N / 2^L = 1
N = 2^L
log N = log(2^L)
log N = L

Thus, our runtime N log N.

Now we introduce insertion sort. Our tree will look something like this.

T(N) = ... -> I(K)
           -> I(K)
             ...x N/K

, - L N/K K. K^2. , :

(N / K) * I(K)
= (N / K) * K * K
= N * K

, , N , . , L ( , K , , ):

N / 2^L = K
N / K = 2^L
L = log (N/K)

,

O(N) = N * K + N * log (N/K)

, , , .

+3

More articles:


All Articles