What Mathematical Technique is used to compare algorithm complexity?

views:

114

answers:

+1 Q:

What Mathematical Technique is used to compare algorithm complexity?

Hi all

I started reading 'Introduction to Algorithms' today, but I've gotten a bit confused over one of the exercises.

Exercise 1.2.2 asks the reader

Suppose we are comparing implementations of Merge sort and Insertion Sort on the same machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge sort runs in 64n log n steps.

For which values of n does insertion sort beat merge sort?

I first tried opening up Wolfram Alpha and using it to draw graphs of the equations, but I couldn't accurately compare the two graphs.

I then tried choosing a random value for n (200), working out the equations on paper, and then modifying the value of n based on my results.
But that took too long.

What is the correct way to solve this exercise?

+4 A:

Is there some value of n where the two are equal?

What happens above that point? Below?

woodchips 2010-08-22 12:46:54

+1 for not giving the answer away.

Joey 2010-08-22 13:08:39

+4 A:

Joey 2010-08-22 12:47:17

Why did You assume log of base 2?

Rekin 2010-08-22 12:54:26

The logarithm doesn't really matter, as he showed the technique in use (use both in a single equation).

Stephen 2010-08-22 12:58:13

@Rekin: Merge sort divides the list into *two* sublists, sorting them individually and then merging them. Which logarithm base would be more appropriate in your eyes?

Joey 2010-08-22 12:59:50

@Hamish: Wrong reasons, kinda. Yes, for talking about complexity classes it's useless to give a specific base, since constant factors are ignored, but in this case we're talking actual performance data (exact numbers of steps). While those follow the complexity class they still have some more detail and to answer the question at hand we actually *need* to use the correct logarithm – in this case base 2, but that's not because of binary representation of numbers but rather an artifact of how Mergesort works.

Joey 2010-08-22 13:01:39

Joey, if you look at the forest, you will tend to give one explanation, and if you look at the trees, you will tend to give another reason.

Hamish Grubijan 2010-08-22 13:10:13

*blinks* and now you got me confused. I was merely noting that the reasons you cite here for the necessity of the binary logarithm has nothing to do with how computers store numbers or even with Landau notation.

Joey 2010-08-22 13:12:12

@Hamish: If you read the link you posted it pretty clearly says that the _algorithm_ brings about the log base two, and doesn't mention the binary representation of numbers at all.

Dolphin 2010-08-23 14:47:21

ansaurus

tags:

views:

answers:

What Mathematical Technique is used to compare algorithm complexity?

related questions