StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h3>Variables</h3> <p><strong>n</strong> = the total amount of items in the set<br> <strong>m</strong> = the amount of unique values that are to be retrieved from the set of n items<br> <strong>d(i)</strong> = the expected amount of tries needed to achieve a value in step i<br> <strong>i</strong> = denotes one specific step. i ∈ [0, n-1]<br> <strong>T(m,n)</strong> = expected total amount of tries for selecting m unique items from a set of n items using the naive algorithm </p> <h3>Reasoning</h3> <p>The first step, i=0, is trivial. No matter which value we choose, we get a unique one at the first attempt. Hence:</p> <blockquote>d(0) = 1</blockquote> <p>In the second step, i=1, we at least need 1 try (the try where we pick a valid unique value). On top of this, there is a chance that we choose the wrong value. This chance is (amount of previously picked items)/(total amount of items). In this case 1/n. In the case where we picked the wrong item, there is a 1/n chance we may pick the wrong item again. Multiplying this by 1/n, since that is the combined probability that we pick wrong both times, gives (1/n)<sup>2</sup>. To understand this, it is helpful to draw a <a href="http://en.wikipedia.org/wiki/Probability_tree" rel="nofollow noreferrer">decision tree</a>. Having picked a non-unique item twice, there is a probability that we will do it again. This results in the addition of (1/n)<sup>3</sup> to the total expected amounts of tries in step i=1. Each time we pick the wrong number, there is a chance we might pick the wrong number again. This results in:</p> <blockquote>d(1) = 1 + 1/n + (1/n)<sup>2</sup> + (1/n)<sup>3</sup> + (1/n)<sup>4</sup> + ...</blockquote> <p>Similarly, in the general i:th step, the chance to pick the wrong item in one choice is i/n, resulting in:</p> <blockquote>d(i) = 1 + i/n + (i/n)<sup>2</sup> + (i/n)<sup>3</sup> + (i/n)<sup>4</sup> + ... = <br/> = sum( (i/n)<sup>k</sup> ), where k ∈ [0,∞]</blockquote> <p>This is a <a href="http://en.wikipedia.org/wiki/Geometric_sequence" rel="nofollow noreferrer">geometric sequence</a> and hence it is easy to compute it's sum:</p> <blockquote>d(i) = (1 - i/n)<sup>-1</sup></blockquote> <p>The overall complexity is then computed by summing the expected amount of tries in each step:</p> <blockquote>T(m,n) = sum ( d(i) ), where i ∈ [0,m-1] = <br/> = 1 + (1 - 1/n)<sup>-1</sup> + (1 - 2/n)<sup>-1</sup> + (1 - 3/n)<sup>-1</sup> + ... + (1 - (m-1)/n)<sup>-1</sup></blockquote> <p>Extending the fractions in the series above by n, we get:</p> <blockquote>T(m,n) = n/n + n/(n-1) + n/(n-2) + n/(n-3) + ... + n/(n-m+2) + n/(n-m+1)</blockquote> <p>We can use the fact that:</p> <blockquote> n/n ≤ n/(n-1) ≤ n/(n-2) ≤ n/(n-3) ≤ ... ≤ n/(n-m+2) ≤ n/(n-m+1)</blockquote> <p>Since the series has m terms, and each term satisfies the inequality above, we get:</p> <blockquote>T(m,n) ≤ n/(n-m+1) + n/(n-m+1) + n/(n-m+1) + n/(n-m+1) + ... + n/(n-m+1) + n/(n-m+1) = <br/> = m*n/(n-m+1)</blockquote> <p>It might be(and probably is) possible to establish a slightly stricter upper bound by using some technique to evaluate the series instead of bounding by the rough method of (amount of terms) * (biggest term)</p> <h3>Conclusion</h3> <p>This would mean that the Big-O order is <strong>O(m*n/(n-m+1))</strong>. I see no possible way to simplify this expression from the way it is.</p> <p>Looking back at the result to <strong>check if it makes sense</strong>, we see that, if n is constant, and m gets closer and closer to n, the results will quickly increase, since the denominator gets very small. This is what we'd expect, if we for example consider the example given in the question about selecting "999,999 values from a set of 1,000,000". If we instead let m be constant and n grow really, really large, the complexity will converge towards O(m) in the limit n → ∞. This is also what we'd expect, since while chosing a constant number of items from a "close to" infinitely sized set the probability of choosing a previously chosen value is basically 0. I.e. We need m tries independently of n since there are no collisions.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload