Suppose you need to generate a random permutation of the first N integers.For example

Chapter 2, Problem 2.8

(choose chapter or problem)

Suppose you need to generate a random permutation of the first N integers.For example, {4, 3, 1, 5, 2} and {3, 1, 4, 2, 5} are legal permutations, but{5, 4, 1, 2, 1} is not, because one number (1) is duplicated and another (3) ismissing. This routine is often used in simulation of algorithms. We assume the existenceof a random number generator, r, with method randInt(i, j), that generatesintegers between i and j with equal probability. Here are three algorithms:1. Fill the array a from a[0] to a[n-1] as follows: To fill a[i], generate randomnumbers until you get one that is not already in a[0], a[1],..., a[i-1].2. Same as algorithm (1), but keep an extra array called the used array. When arandom number, ran, is first put in the array a, set used[ran] = true. This meansthat when filling a[i] with a random number, you can test in one step to seewhether the random number has been used, instead of the (possibly) i steps inthe first algorithm.3. Fill the array such that a[i] =i+1. Thenfor( i = 1; i < n; i++ )swapReferences( a[ i ], a[ randInt( 0, i ) ] );a. Prove that all three algorithms generate only legal permutations and that allpermutations are equally likely.b. Give as accurate (Big-Oh) an analysis as you can of the expected running time ofeach algorithm.c. Write (separate) programs to execute each algorithm 10 times, to get a goodaverage. Run program (1) for N = 250, 500, 1,000, 2,000; program (2) forN = 25,000, 50,000, 100,000, 200,000, 400,000, 800,000; and program (3) forN = 100,000, 200,000, 400,000, 800,000, 1,600,000, 3,200,000, 6,400,000.d. Compare your analysis with the actual running times.e. What is the worst-case running time of each algorithm?