- 1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in $8n^2$ steps, while merge sort runs in $64n \lg n$ steps. For which values of $n$ does insertion sort beat merge sort?
- The question is essentially asking for which values of $n$ is $8n^{2} \lt 64n \lg n$. We can solve this question by first factoring out an $8n$ and we get $n \lt 8 \lg n$
Unfortunately this problem is not solvable using elementary operations. Luckily we are being asked for an integer solution (as computers operate in discrete steps) and we could use the underutilized guess-and-and method.

$n$ $8 \lg n$ 14 30.46 41 42.86 43 43.41 44 43.675 - 1.2-3 What is the smallest value of n such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine.
- This question is asking us find the smallest positive integer $n$ that satisfies $100n^{2} \lt 2^n$. This could be solved by doing the math, by looking at a plot of the curves, or using the above method again. . $$2^{14} = 16384$$ $$(100 \times 14^{2}) = 19600$$ $$2^{15} = 32768$$ $$(100 \times 15^{2}) = 22500$$ An exponential algorithm becomes far worse than a polynomial algorithm when we have only 15 items to worry about. In other words: avoid exponential algorithms!

**Updated 2012-09-05:**I had a brain lapse the day I originally published this and accidentally used the natural logarithm instead of the base 2 log for question 1.2-2. How I ever managed to do that I will not know, but I've fixed it.

Merge sort running time is proportional to nlog n

ReplyDeletewhere log is taken to the base 2 and not the natural logarithm.

The correct answer is insertion sort is quicker for n belongs to [2,43](closed interval).

How do you solve this algebraically to get 2<=n<=43?

ReplyDeleteHow do you solve this algebraically to get 2<=n<=43?

ReplyDeleteAnonymous, oops, I must have had a massive brain lapse that day. I fixed the post - thank you!

ReplyDeleteI am not getting the solution of 1.2-2.Can you please elaborate it.Thanks for the nice post.

ReplyDelete