Theoretical exercise 5 Always analyze the running time, and explain why the algorithm is correct. Write only pseudo codes.

4. Question 4: Given two arrays A, B each of size n, and say that all elements in A are pairwise distinct and so are the elements of B. Give a randomized algorithm that checks if the sorted arrays of A and B are the same, with the lowest possible expected running time.