a) Given an Array of n numbers. Prove that using a deterministic algorithm the most efficient run time to verify whether the array is Sorted or "Mostly Sorted (9/10)*n items in the correct positions.

b) Now lets add randomness. One property of a sorted array is that any consecutive three elements in the array are also sorted. As a first try, our algorithm will repeatedly sample consecutive triples of elements and check whether the triple is sorted. The algorithm will output SORTED if and only if all sampled triples are sorted.

Let the number of sampled triples be k. Show that we must have k be (n) for the probability of success of this algorithm to exceed a .

Hint: It suffices to demonstrate a single adversarial input. Hint: (1 1 )^n e^(1). You may also find the inequality 1 x e^(x) useful.