Worst-case expected running time for Randomized Permutation Algorithm

Question

I have an algorithm which, when given a positive integer N, generates a permutation of the first N integers (from 1 to N) using a method called randInt(x,y). The method randInt(x,y) will generate a random integer between the numbers x and y, provided they are positive integers and y >= x.

The algorithm is given by the following pseudo-code:

1.  if (N <= 0) {
2.     return null
3.  } else {
4.     A := new int[] w/ size N and all cells initialized to 0
5.     a[0] := randInt(1,N)
6.     for (i := 1 to length(A)-1) do 
7.        boolean rInA := True
8.        while (rInA) {
9.           rInA := False 
10.          int r := randInt(1,N)
11.          for (j := 0 to (i-1)) do 
12.             if (r = A[j]) {
13.                rInA := True
14.             }
15.          }   
16.       }
17.       A[i] := r
18.    }
19. }
20. return A

My understanding of the algorithm is as follows:

The outermost for-loop will run N-1 times and for each of those iterations a random number is generated and then compared to all the previous cells of A that have been visited in previous iterations. If any of the those cells contain that randomly generated number then that number cannot be used and a new number is randomly generated (in the next iteration of that nested while-loop). This new randomly generated number is then, like before, compared to all the previously visited cells in A to check for duplication. This continues until randInt(x,y) generates a random number that is not already in the first i cells of A.

This leads me to believe that the Worst-case expected running time of the algorithm is something like: $\sum_{i=1}^{N-1}(\alpha i)$

Now the $\alpha$ here represents the effect the while-loop has on the running time and is the point of uncertainty for me. I know that in the first iteration of the outermost for loop its unlikely that randInt will generate the one integer that A already contains (1/N I believe) so that inner-most for-loop is likely to only execute once. However, by the last iteration (of outer-most for-loop) the probability that randInt generates one of the N-1 integers already in A is $\frac{N-1}{N}$ so because of the while-loop its likely that the inner-most for-loop for that iteration (of the outer-most for-loop) will execute more like n times.

How can I use the probability introduced into the algorithm by randInt to calculate the algorithms run-time?

Answer 1

Firstly I would revise the inner for loop so that checking whether $r$ has been used already, is $O(1)$. As stated, it is $O(n)$. You could do this by initializing a (1-indexed) boolean array $used[\cdot]$ of length $n$, and setting $used[x]$ equals true whenever you set some $A[i]=x$.

Now the question is how many times may $rand()$ be called in the worst case. Actually, the way the algorithm is set up right now, the worst case is $+\infty$; this is because it's not learning from any of its bad choices of $r$. For instance, if it selects $5$, when $5$ was already in $A$, then the smart thing to do would be never to guess $5$ again. There are ways to achieve this; so if you had some method that never repeated guesses, then you can get $O(n^2)$ worst case runtime.

If you are interested in expected runtime, then you can calculate the expected number of times $r$ is recalculated in any given step: at step $i$, there are $n-i$ good choices, for a success probability of $\frac{n-i}{n}$. The expectation for number of tries to get a first success in a bernoulli variable with probability $p$, is $\frac{1}{p}$. Then if you sum $\frac{n}{n}+\frac{n}{n-1}+\frac{n}{n-2}+\cdots \frac{n}{1}$ you have asymptotic $O(n\log n)$. This is basically the coupon collector's problem.