Question

Amortized Analysis
What would be the amortized analysis of the following algorithm:
```
function listRandomUnique(count, range) {
var list = [];
while (list.length < count) {
var x = Math.floor(Math.random()*range);
if (list.indexOf(x) === -1) {
list.push(x);
}
}
return list;
}
```

Answer 1

@e.mccormick
What makes it an interesting question is that we have a random variable.

Answer 2

Technically speaking, it could never halt. That is the worst case scenario, but realistically it should eventually halt.

Answer 3

We can say \(n\) is the range, and \(k\) is the count. The point here is to get \(k\) integers between \(0\) and \(n\).

Answer 4

At the start, your probability of having to call `Math.random()` again is \(0/n\). But the next time it would be \(1/n\).

Answer 5

When you're trying to get the \(k\)th random integer, you'd have \((k-1)/n\) probability of having to go again.

Answer 6

This is almost more of a probability question than a computer science one.

Answer 7

The worst case scenario or never halting is sort of a useless analysis. I guess the average case scenario is more helpful.

Answer 8

If we say \(r\) is the number of times that `Math.random()` is called, we'd be looking for the expected value of \(r\) in terms of \(n,k\).

Answer 9

Start with \(i=0\), we call it once. \(1\).
When \(i=1\) we call it once. \(1\).
Then we have \(1/n\) probability we need to call it again. It's a geometric distribution.

Answer 10

\[
E[r]=\sum_{i=0}^{k-1}\frac{n}{n-i}
\]

Answer 11

This line is confusing me, does it create a random double between 0 and x?
```
var x = Math.floor(Math.random(x));
```

Answer 12

And how is the parameter range used in the function?

Answer 13

Haven't seen an argument passed into the Math class's random method before. Just what the no-arg method call results in.

I wonder what happens.

Answer 14

ah gotcha.