Category Archives: Introduction to Algoritms

Information Technology (IT), Introduction to Algoritms

“Introduction to Algorithms” Exercise 1.2-2

2 Comments

I’ve just started reading “Introduction to Algorithms,” Third Edition, by Cormen, Leiserson, Rivest, and Stein as part of my self-designed, self-taught course in making me a better software developer. I’m two sections in to the first chapter, and what I’m realizing I’m going to need to study up on some fairly elementary algebra. But, I stumbled my way through a problem with base 2 logarithms in play. Here’s my victory for today.

The question was this:

1.2-2  Suppose we are computing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort?

So, I set up the equation:

8n2 < 64n lg n

Divide by 8, and we get:

n2 < 8n lg n
Or: (n)(n) < 8n lg n

So, divide both sides by n and get:

n < 8 lg n

If we then divide both sides by 8, we end up with:

n/8 = lg n

Now, multiply both sides by 1/n, and we get:

1/8 = lg n / n

Beyond that point, I just pulled out my calculator and started inserting numbers for n and figuring out whether or not the statement was true, as follows:

n = 10:      .1250 < .3322 = TRUE
n = 1:         .1250 < 0 = FALSE
n = 2:         .1250 < 5 = TRUE
n = 20:      .1250 < .2161 = TRUE
n = 30:      .1250 < .1636 = TRUE
n = 40:      .1250 < .1774 = TRUE
n = 50:      .1250 < .1129 = FALSE
n = 45:      .1250 < .1220 = FALSE
n = 44:      .1250 < .1241 = FALSE
n = 43:      .1250 < .1262 = TRUE

So, for integer values (since we can only sort whole numbers of items):

2 <= n <= 43

Now, I’ve only got a natural logarithms button on my Texas Instruments BAII Plus calculator (at least, I’m only AWARE of natural logarithms button on that calculator), so I had to search the web to figure out that to get Log2(x) I could divide Ln(x) by Ln(2) (thanks to TVMCalcs.com for that assist!).

If anyone could remind me of a better way to figure out the range of acceptable answers here than the “guess and check” with the calculator, please leave a comment.  Such would be greatly appreciated!  But, I’m glad I was at least able to come up with an answer this way, and wanted to post about it.