Question 4: (30 points) Consider the bubble-sort algorithm below. Algorithm 1 BUBBLESORT(A, n) 1: Input: array A of n numbers 2: Output: sorted array A 3: for i 4: Bubble the largest of A[o..i] down to position Ai 5: for j 0 to i-1 do 6: 7: n-1 downto 1 do if (A[jl > Ait 11) then SWAP(AGI, AG + 11) end if 9: end for 10: end for (a) Analyze the worst-case time complexity, T(n) (b) Rewrite the bubble-sort algorithm using recursion (c) Let f(n) be the worst-case number of key-comparisons used by this algorithm to sort rn elements. Write a recurrence for f(n) and solve it by repeated substitution method. (d) Prove the correctness of the bubble-sort algorithm above Hint: Find a property of the array A at the end of each iteration of the outer loop. Prove this property by induction