2. Consider the following algorithm: Bogosort 1. input Array a[i...n] 2. 3. randomly permute a[1...n] 4. for i = 1 to n-1 if a[i] > a[i+1] 6 goto 3 7. return a (a) For an input of size n, what is the best case performance in terms of n? (b) Assume is a random permutation of the array a. Define C to be the random variable that counts the number of comparisons carried out to test whether is sorted in lines 4-6. What is EC? Hint: Taylor Series expansion ofe*'z'A (c) What is the average runtime of Bogosort