For inputs of size n, for which values of n does i

问题:

In the book Introduction to Algorithms (Corman), exercise 1.2-2 asks a the following question about comparing implementations of insertion sort and merge sort. 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?

Although I am interested in the answer, I am more interested in how to find the answer step by step (so that I can repeat the process to compare any two given algorithms if at all possible).

At first glance, this problem seems similar to something like finding the break even point in business-calculus, a class which I took more than 5 years ago, but I am not sure so any help would be appreciated.

Thank you

P/S If my tags are incorrect, this question is incorrectly categorized, or some other convention is being abused here please limit the chastising to a minimum, as this is my first time posting a question.

回答1:

Since you are to find when insertion sort beats merge sort

8n^2<=64nlogn
n^2<=8nlogn
n<=8logn

On solving n-8logn = 0 you get

n = 43.411

So for n<=43 insertion sort works better than merge sort.