Problem 2. Comparing: I have two algorithms, A and B, that are used to change the ordering of an array of n elements. A usesn2 operations, whereas B uses n log(n) operations. Which algorithm should one prefer and why?

Problem 3. Bubblesort: Consider the following pseudocode for bubblesort:bubblesort(A, n)for i from 1 to n 1for j from n to i + 1if A[j] < A[j 1]swap(A[j], A[j 1])

(a) What is the loop invariant for bubblesort?

(b) State briefly a proof of correctness.

(c) Derive concisely the worst-case running time of bubblesort as a function of the input array sizen? Show your work!

(d) Derive concisely the best-case running time as a function of n. Show your work.

Problem 4. Merge: You are given two sorted arrays, array A of size n and array B of size m. Write pseudo-code for theMerge procedure that merges arrays

A and B into a new sorted array C. You can assume C has beenpreallocated to have the right size.