Problem:
Suppose you are given $ k $ sorted arrays, each with $ n $ elements, and you want to combine them into a single array of kn elements. Consider the following approach. Divide the $ k $ arrays into $ k/2 $ pairs of arrays, and use the Merge subroutine taught in the MergeSort lectures to combine each pair. Now you are left with $ k/2 $ sorted arrays, each with $ 2n $ elements. Repeat this approach until you have a single sorted array with kn elements. What is the running time of this procedure, as a function of $ k $ and $ n $?
Solution:
The first iteration deal with $ \frac{k}{2} $ array of length $ n $, so it takes $ \theta(nk) $ time.
The second iteration deal with $ \frac{k}{4} $ array of length $ 2n $, so it also takes $ \theta(nk) $ time.
Therefore the overall execution time is really just $ \theta(nk\log k) $ time.
This is simply and I should have got this correct, I made a careless mistake here, sigh.
Suppose you are given $ k $ sorted arrays, each with $ n $ elements, and you want to combine them into a single array of kn elements. Consider the following approach. Divide the $ k $ arrays into $ k/2 $ pairs of arrays, and use the Merge subroutine taught in the MergeSort lectures to combine each pair. Now you are left with $ k/2 $ sorted arrays, each with $ 2n $ elements. Repeat this approach until you have a single sorted array with kn elements. What is the running time of this procedure, as a function of $ k $ and $ n $?
Solution:
The first iteration deal with $ \frac{k}{2} $ array of length $ n $, so it takes $ \theta(nk) $ time.
The second iteration deal with $ \frac{k}{4} $ array of length $ 2n $, so it also takes $ \theta(nk) $ time.
Therefore the overall execution time is really just $ \theta(nk\log k) $ time.
This is simply and I should have got this correct, I made a careless mistake here, sigh.
No comments:
Post a Comment