Question

Mergesort is known to be one of the fastest algorithms for sorting lists of data. In fact, the runtime of mergesort is proportional to n· logn where n is the size of the list to be sorted. Bubblesort, on the other hand is a much slower algorithm, since it's runtime is proportional to n² , where n is the size of the list to be sorted.

As an experiment, mergesort is run on a slow computer, bubblesort is run on a fast computer and the times taken by each algorithm are recorded when sorting a list of size 10,000. We are surprised to find that the two runtimes are identical. In other words, the faster computer appears to have compensated for the slowness of bubblesort, relative to mergesort. To see whether this result remains true for bigger input sizes, we will redo the experiment, but use a list of size one hundred million, rather than ten thousand. After recording the new runtimes we will compute the ratio r = (new runtime of bubblesort) /  (new runtime of mergesort).

a) What should we predict the value of r to be? _________________

Your answer should be a whole number. For example, you would answer r = 1, if you think the algorithms still take the same amount of time. Or you would answer r = 2, if you think bubblesort takes twice as long a mergesort, and so on.

b) Justify your answer in Part a using runtime rules of thumb that we discussed in lecture.  (A detailed justification is needed here, involving some arithmetic.)

Answer 1

a)r=2
as this time the number of elements is way larger and fast computer wont compensate the large amount of steps added. this time.

===========================================================================

b)In case of bubble sort its complexity is O(n^2) that is if there are 10 elements to be sorted it would take 100 steps to sort the list.
but in case of merge sort its complexity is O(n*logn) that is in case of 10 elements it would take 10 steps to sort the list.
Bubble sort works best for small data elements but in case of large data it fails due to complexity of O(n^2) due to which there are lot of comparisons to be made.
In this case of having elements of one hundred million the steps in bubble sort will be twice of 100 million but it will be way less in merge sort and also merge sort runtime is not affected as the number of elements are larger or not.
But as bubble sort is being run on the fast computer which showed results same for 10000 elements as in case of 10000 elements number of steps in merge sort will be 40000 and in bubble sort it will be 10^8 the fast computer have compensated the loss of bubble sort and the runtime ratio will be 1 but now in case of 100 million, if we find out the complexity of bubble sort then O(n^2) then it will come to be 10^16 and in case of merge sort the complexity O(n.logn) the number comes out to be 800 million the steps are too much in case of bubble sort and if we compute the ratio of bubble sort and merge sort then it goes way beyond the charts in case of 100 million list elements and the fast computer will not be able to compensate this time and steps difference will be way larger to be compensated and thus, it can be concluded that bubble will take twice the time than the merge sort and runtime ratio will be 2.