Programming Assignment 1 100 points Implement a program that

•Programming Assignment 1 (100 points)

•Implement a program that finds the zero of a function

•Use the function for your testing to be that defined in problem 1.2-2,

•f(n) = 8n2 – 64n lg n

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 8n2 steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort?

\"I WANT PROGRAM FOR THE ABOVE QUESTION\"

Solution

Answer :

    For insertion sort to beat merge sort for inputs of size n, 8n² must be less than 6n log n.

8n² < 64n log n ==>n/8 < log n ==> 2^n/8 < n

This is not a purely polynomial equation in n. To find the required range of values of n, either we have to manually calculate the values of these expression for different values of n or use Newton;s Method or plot these functions or write a piece of code to found the values. For this exercise, I\'ll verifly describe all of these methods but going forward I\'ll mostly use calcutions that can be done with scientific calculator and python codes.

It is obvious that insertion sort runs at quadratic time which is definitely worse than merge sort;s linearithmic time for very large values of n, We know for n = 1, merge sort beats insertion sort. But for values greater than that, insertion sort beats merge sort. So, we will start checkin from n = 2 and go up to see for what value of n merge sort again starts to beat insetion sort.

Notice that for n < 8, 2^n/8 will be a fraction. So, let;s start with n = 8 and check for values of n which are power of 2.

n = 8 ===> 2^8/8 = 2¹ = 2 < 8

n = 16 ===> 2^16/8 = 2² = 4 <16

n = 32 ===> 2^32/8 = 2⁴ = 16 < 32

n = 6 ===> 2^64/8 = 2⁸ = 256 > 64

Some where between 32 and 64, merge sort starts to beat insertion sort. Let\'s do what we were doing but now we are going to try value of either range, repeatedly ( binary search ).

n = 32 + 64 /2 = 48 ===> 2^48/8 = 64 > 48

n = 32 + 48 / 2 = 40 ===> 2^40/8 = 32 < 40

n = 40 +48 / 2 = 44 ===> 2^44/8 = 44.8 > 44

n = 40 + 44 /2 = 42 ===> 2^42/8 = 38.4 < 42

n = 42+ 44 / 2 = 43 ===> 2^43/8 = 42.4 < 43

So, at n = 4, merge starts to beat insertion sort again. Therefore, for 1 < n < 44, Insertion sort bears merge sort.