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 \ln 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 \ln n$. We can solve this question by first factoring out an $8n$ and we get $n \lt 8 \ln 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 \ln n$
14	21
41	29.7
20	23.9
25	25.6
26	26.01
27	26.3

So there we have it: given this data we would prefer insertion sort whenever we have fewer than 27 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.