a) Suppose the runtime of a computer program is proportional to the square of the input size. Using the notation from lecture, that means T(n) = kn^2 where T(n) is the runtime, n is the input size and k is a constant. In lecture, we used a chain of inequalities to derived a rule that applies when the input size is doubled. This time we are going to derived a rule that applies when the input size is squared. To do so, complete the following chain of inequalities:

T(n^2) = k(n^2)^2) = k(n^2)(n^2) = ______________ = ________________. The first blank should just rearrange the factors to put on of the n^2 factors in front. The last blank should be an expression involving T(n).

Now express the algebraic result above as a rule of thumb in the style from lecture. The rule should be something like " If we square the input size, the runtime is multiplied by ____________________________________. "

b) Recall from lecture, we showed that the runtime of bubblesort is approximately proportional to n^2 where n is the list size. Given this result, and your rule of thumb from Part a, how many milliseconds would you expect bubblesort to take to process a list of size four hundred million, given that it takes 200ms to process a list of size twenty thousand? Use the rule of thumb from Part a, and show your work. ALSO, after you get a result in milliseconds, convert that result into hours, minutes and seconds. Show complete work for the unit conversion. (Don't just write a result.)

c) A faster sorting algorithm than bubblesort is mergesort, which has runtime approximately proportional to the nlogn, where n is the list size. Suppose mergesort is run on a very slow computer relative to the computer used for bubblesort and in that scenario, mergesort also takes 200ms to process a list of size twenty thousand. Use a rule of thumb from lecture to calculate the runtime in milliseconds when we increase the list size to four hundred million. ALSO, after getting the result in milliseconds, convert that result to minutes and seconds. (Again, show work for the unit conversion.) You should use an existing rule of thumb from lecture for this problem. Do not use algebra or attempt to rederived a rule anywhere in your answer.