Why is the Big-O of this algorithm N^2*log N
algorithm, big-o, java, permutation
Solution
The `0` entry is filled immediately. The `1` entry has probability `1 - 1 / n = (n - 1) / n` of getting filled by a random number. So we need on average `n / (n - 1)` random numbers to fill the second position. In general, for the `k` entry we need on average `n / (n - k)` random numbers and for each number we need `k` comparisons to check if it's unique.
So we need
n * 1 / (n - 1) + n * 2 / (n - 2) + ... + n * (n - 1) / 1
comparisons on average. If we consider the right half of the sum, we see that this half is greater than
n * (n / 2) * (1 / (n / 2) + 1 / (n / 2 - 1) + ... + 1 / 1)
The sum of the fractions is known to be `Θ(log(n))` because it's an harmonic series. So the whole sum is `Ω(n^2*log(n))`. In a similar way, we can show the sum to be `O(n^2*log(n))`. This means on average we need
Θ(n^2*log(n))
operations.
Problem
Fill array a from a[0] to a[n-1]: generate random numbers until you get one that is not already in the previous indexes. This is my implementation: ``` public static int[] first(int n) { int[] a = new int[n]; int count = 0; while (count != n) { boolean isSame = false; int rand = r.nextInt(n) + 1; for (int i = 0; i < n; i++) { if(a[i] == rand) isSame = true; } if (isSame == false){ a[count] = rand; count++; } } return a; } ``` I thought it was N^2 but it's apparently N^2logN and I'm not sure when the log function is considered.