Input: data: array with n integers Input: n: size of data Output: permutation of data such that data[1] data[2] ... < data[n] 1 Algorithm: StoogeSort 2 if n1 then 3 return data 4 else if n 2 then if data[1]>data[2] then end Swap them third [n/3] return data 9 else 10 11 12 13 14 StoogeSort(data[1..n-third]) 15 end StoogeSort(data third..n]) StoogeSort(data[1..n-third]) return data 1. Develop a recurrence for the worst case time complexity of the StoogeSort algorithm above. Show your work. Note: StoogeSort is a joke sorting algorithm. It is correct but has poor performance. 2. Use the Master Theorem to solve your recurrence in the previous question. Show your work. If the Master Theorem does not apply, explain why it does not. 3. Sketch and analyze a recursion tree for the recurrence T(n) 21(n/4)+ e(n). You may use the Master Theorem to check your work, but only your recursion tree will be considered. 4. Suppose that data is an array of size n that contains the value n followed by 1 to -1. For example, if n = 5, data =[5, 1,2,3,4]. What sorting algorithm would you recommend to use to sort data? Briefly justify your answer.