(Solved): Problem 6: Consider a non-deterministic algorithm that sorts a list of \( n \) elements by randomly ...

Problem 6: Consider a non-deterministic algorithm that sorts a list of \( n \) elements by randomly choosing a permutation \( p \) of \( n \) elements, and then assigning \( a_{1}:= \) \( a_{p(1)}, a_{2}:=a_{p(2)}, \ldots, a_{n}:=a_{p(n)} \) (note, a permutation on \( n \) elements is a bijection from \( \{1,2, \ldots, n\} \) to itself). Our program keeps looping while any element of the list is out of order, so if one permutation doesn't work, a new one is chosen at random and we try again. (a): What is the best-case time complexity for this algorithm? What is the worst-case time complexity for this algorithm? Hint: is it possible to keep getting unlucky with your random permutation? \( (\alpha) \) : (optional) How long would you expect this program to take on average, assuming (perhaps unrealistically) we can check whether the list is in order in one fixed-time step?