Reference no: EM132432197

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 <cstdlib>
#include <algorithm>
#include <vector>

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)
{
  // Array of booleans: used[k] is true if we have already
  // put k somewhere into the array a
  bool* used = new bool[n];
  fill (used, used+n, false);
  for (int i = 0; i < n; i++)
    {
      // Guess at a value to put into a[i]
      a[i] = rnd(n);
      while (used[a[i]])
        {
	 // If it's one that we've already used, guess again.
         a[i] = rnd(n);
        }
      used[a[i]] = true;
    }
  delete [] used;
}