3 questions

thank you

a) Modify our analysis of bubble sort to count the number of item comparisons fike before) P(US the number of assignments involving a swap. That means In the body of the inner loop there are four things to count: The one item comparison plus the tree assigniments in the swap. Assume a worst ease scenario Where we will actually do a swap for each iteration or the inner loop. You should get a simple formula. b) Repeat Part a for selection sort Before working on this, please read the bubblesort notes and watch Lectures 3 and 4. a) How many swaps are performed by bubblesort, when the list of numbers is initially in descending order? b) How many swaps are performed by bubblesort, when the list of numbers is initially in ascending order? Justify your answers. 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(n2)=k(n2)2)k(n2)(n2)= The first blank should just rearrange the factors to put on of the n2 factors in front. The last blank should be an expression involving - Tin). Now express the aggebraic 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 n2 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 milifieconds, comvert that result into hours, minutes and seconds. Show comelete work for the unit conversion, (Don't just write a result) c) A faster sorting algorithm than bubblesort is mersecort, which has runtime approximately proportional to the nlogn. where n is the list slee. Suppose mergesort is run on a very slow computer relative to the computer used for bubblesort and in that scenario, mergesort also takes 200m to process a list of size twenty thousand: Use a rule of thumb from lecture to calculate the runtime in malliseconds when we increase the list sixe to four hundred mililion. ALso after getting the rexult in miliseconds, convert that result to minuter and seconds. (Again show work for the unit conversion) Yau should ube an existing rule of thumb from lecture for this problem. Do not ve algebea oratterept to rederived a nule arywhere in your