Mergesort is known to be one of the fastest algorithms forsorting lists of data. In fact, the runtime of mergesort isproportional to n· logn where n is the size of the list to besorted. Bubblesort, on the other hand is a much slower algorithm,since it's runtime is proportional to n2 , where n isthe 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 eachalgorithm are recorded when sorting a list of size 10,000. We aresurprised to find that the two runtimes are identical. In otherwords, the faster computer appears to have compensated for theslowness of bubblesort, relative to mergesort. To see whether thisresult remains true for bigger input sizes, we will redo theexperiment, but use a list of size one hundred million, rather thanten thousand. After recording the new runtimes we will compute theratio 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 wouldanswer r = 1, if you think the algorithms still take the sameamount of time. Or you would answer r = 2, if you think bubblesorttakes twice as long a mergesort, and so on.
b) Justify your answer in Part a using runtime rules of thumbthat we discussed in lecture.  (A detailedjustification is needed here, involving some arithmetic.)
