Accurate Big-O analysis

Question

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) is missing. This routine is often used in simulation of algorithms. We assume the existence of a random number generator, RandInt(i,j), that generates between i and j with equal probability. Here are three algorithms:

(i) Fill the array A from A[0] to A[N-1] as follows: To fill A[i], generate random numbers until you get one that is not already in A[0], A[1],…, A[i-1].

(ii) Same as algorithm (i), but keep an extra array called the Used array. When a random number, Ran, is first put in the array A, set Used[Ran] = true. This means that when filling A[i] with a random number, you can test in one step to see whether the random number has been used, instead of the (possibly) i steps in the first algorithm.

(iii) Fill the array such that A[i] = i+1. Then

for (i=1; i<n; i++)
swap (A[i], A[RandInt(0,i)]);

Give as accurate (Big-O) an analysis as you can of the expected running time of each algorithm.

Anyone can help with this? Cause i just learn this chapter and not quite understand what the question wants..

Answer 1

I: You have to fill N slots, but as you keep filling you are less likely to get a valid number. If you have filled M slots, then the chance of getting a valid number is 1-(M/N). In addition, as the list gets longer, you need to iterate over the entire thing. N numbers * O(N) guesses per slot * O(N) checks to see if number is already contained = O(N^3) (O(N) checks per number because worst case is last number, 1/N chance to get unused one)

II:Now we don't have to iterate over the entire array for each check, so only O(N^2)

III: Swapping takes constant time, and we iterate over the entire array once, so O(N)

I think I did all those correctly, but I easily could have missed something. Hope this helps.

Answer 2

Option 4 : Fill a List / Collection with values from 1 to n, then shuffle the Collection. O(n) + ~O(n) => O(n)