# Naïve array sampling algorithm: the possibility of a item being chosen and its time complexity

This naïve sampling algorithm I am talking about is fairly simple: create a set for storing chosen items first, randomly select an item from the array, and examminate if it is in the set. If it isn't, add it to the set, otherwise we will skip and reselect. This process will be repeated until required amount of samples are seccessfully selected.

Following is the JavaScript version of the algorithm (fell free to paste it into a browser console and try it):

function sample(arr, n) {
if (n >= arr.length) return arr.slice(0);

let set = new Set();
while (set.size < n) {
let index = Math.floor(Math.random() * arr.length);
if (set.has(index)) continue;
}

let result = [];

for (let index of set) {
result.push(arr[index]);
}

return result;
}


Although is simple, it is difficult for me to find out the time complexity, and the possibility for each array items to be chosen. If the algorithm is practical, it should garentee every items has equally $$k/N$$ possibility to be selected, when we select $$k$$ items from an array with $$N$$ items. Unfortunately, I cannot prove this.

The time complexity is hard to handle with too, because the algorithm is based on random selecting, so it is possible that we happen to select the same item for many times, and as more and more items are selected, this possibility will increase, which makes the time complexity harder to compute.

Assume that $$m$$ items have already been chosen. The next one needs to be different, which occurs with probability $$1-\dfrac mn$$. So the expectation of the number of drawings is $$\dfrac{n}{n-m}$$ (geometric law). To reach the quorum of $$k$$ numbers, you will need
$$\sum_{m=0}^{k-1}\frac n{n-m}=n\left(H_{n}-H_{n-k}\right)\sim n\log\frac n{n-k}\\\sim k\ \text{ if }k\ll n$$ drawings on average, each corresponding to a search in the current set. To this, you add $$k$$ insertions.