Use the copy-and-paste method to give an average-case analysis for the permute function in permute.cpp.

Assume that the random number generator used in the algorithm produces truly random numbers, i.e, for any integer j in the range 0 .. RAND_MAX, any given call of rand() has a probability 1/RAND_MAX of returning j.

The rand() function runs in O(1) time (worst-case and average).

Show all work!

Remember that you are doing average case analysis.

#include

#include

#include

using namespace std;

unsigned rnd(unsigned limit)

{

return rand() % limit;

}

// Generate a random permutation of the integers from

// 0 .. n-1, storing the results in array a.

//

void permute (int a[], int n)

{

for (int i = 0; i < n; i++)

{

// Guess at a value to put into a[i]

int guess = rnd(n);

while (find(a, a+i, guess) != a+i)

{

// If it's one that we've already used, guess again.

guess = rnd(n);

}

a[i] = guess;

}

}