1.Argue that the inner while loop in MysterySort (lines 48) iterates a total of n times when MysterySort is called on an array of size n.

2. Identify the worst-case time complexity for MysterySort. Justify your answer. You may assume that elements of the array can be marked in (1) time.

3. Suppose that RecursionMystery is an algorithm that takes in an array of size n, makes 4 recursive calls with arrays of size n/2, and takes (1) time otherwise. Identify the worst-case time complexity for RecursionMystery. Show your work. You may use the fact that the sum of any exponentially increasing series is dominated by its last term

Input: data: array of n distinct elements Input: n: size of data Output: permutation of data such that data] datal2] sdataln 1 Algorithm: MysterySort 2 while we haven't marked n elements of data do Let data be the first unmarked element of data 4while datar] is not marked do Let Itz be the number of elements of data that are Swap data[ltr] Mark datalltr data and datalr end 9 end o return data