2
$\begingroup$

I am learning algorithms from the CLRS book on my own, without any help. It has an exercise which combines merge sort {O(n log n)} with insertion sort {O($ n^{2} $)}. It says that when the sub-arrays in the merge-sorting reach a certain size "k", then it is better to use insertion sort for those sub-arrays instead of merge sort. The reason given is that the constant factors in insertion sort make it fast for small n. Can someone please explain this ?

It asks us to show that (n/k) sublists, each of length k, can be sorted by insertion sort in O(nk) worst-case time. I found from somewhere that the solution for this is O($ nk^{2}/n $) = O(nk). How do we get this part O($ nk^{2}/n $) ?

Thanks !

$\endgroup$
3
$\begingroup$

For your first question:
O(n logn) might be 4nlogn or 13nlogn or 0.1nlogn etc.

If you compare 4n^2 and 100nlogn you will see that for n < about 200 the O(n^2) is faster. Big O is an asymptotic measure. It says what happens when n approaches infinity, but does not say anything about “smaller” inputs.

For your second question:
You have n/k sublists. Each sublist has length k and needs k^2 to be sorted with insertion sort. So multiply and you get n/k * k^2 = nk worst case. This is a way of parametrizing your algorithm’s complexity. If you choose k to be a constant c ex. k = 3 then you have n/3 sublists of length 3. Each one needs 3^2 = 9 execution steps and the overall amount of work is n/3 * 9 = 3n. You can also choose k to be a function of n, ex. k = f(n) = n/5. Then you have n/(n/5) = 5 sublists of length n/5. Each sublist needs (n/5)^2 = n^2/25 execution steps and the overall amount of work is 5 * n^2 /25 = n^2 / 5. Again, don’t assume that the one is faster than the other. n^2 / 5 and 3n describe “the same thing” written differently.

Finally, keep in mind that big O describes neither time nor space. It describes amount of work it needs to be done. If you take account the parallelization then for example assuming an ideal choice of pivots, parallel quicksort sorts an array of size n in O(n log n) work in O(log² n) time using O(n) additional space.

Some algorithms can be parallelized and some others can’t. Insertion sort for example is CPU favorable when the input size is comparable to the “block size” of the CPU. Divide and conquer algorithms are not fast for small inputs because the cpu must populate the code recursively. This means lot of memory to be allocated, lot of stacks, etc

The approach you are describing is a hybrid algorithm.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.