Thursday, June 23, 2011

Blogging my way through Cormen [2/?]

As I said in part 1 I am reading a book on algorithms and have decided to blog my way through. My primary goal in doing so is to improve my writing skills. A secondary goal is to force myself to actually answer the questions.

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
So there we have it: given this data we would prefer insertion sort whenever we have fewer than 43 items.
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!
Thank you JT and JM for giving me the idea to go through the book, and for looking at my posts before I publish them.
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.

5 comments:

  1. Merge sort running time is proportional to nlog n
    where 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).

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

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

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

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

    ReplyDelete

Have something you want to say? You think I'm wrong? Found something I said useful?
Leave a comment!