StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Another idea based on balanced binary search tree, as in <a href="https://stackoverflow.com/users/540026/keith">Keith</a>'s answer. </p> <p>Suppose all inserted elements so far are stored in balanced BST, and we need to compute <code>minmod(m)</code>. Consider our set <code>S</code> as a union of subsets of numbers, lying in intervals [<strong>0,m-1], [m, 2m-1], [2m, 3m-1]</strong> .. etc. The answer will obviously be among the minimal numbers we have in each of that intervals. So, we can consequently lookup the tree to find the minimal numbers of that intervals. It's easy to do, for example if we need to find the minimal number in <strong>[a,b]</strong>, we'll move left if current value is greater than <strong>a</strong>, and right otherwise, keeping track of the minimal value in <strong>[a,b]</strong> we've met so far.<br/></p> <p>Now if we suppose that <strong>m</strong> is <strong><em>uniformly distributed</em></strong> in <strong>[1, 2^64]</strong>, let's calculate the mathematical expectation of number of queries we'll need. <br/></p> <p>For all <strong>m</strong> in <strong>[2^63, 2^64-1]</strong> we'll need <strong>2</strong> queries. The probability of this is <strong>1/2</strong>.<br/> For all <strong>m</strong> in <strong>[2^62, 2^63-1]</strong> we'll need <strong>4</strong> queries. The probability of this is <strong>1/4</strong>.<br/> ...<br/> The mathematical expectation will be <strong>sum[ 1/(2^k) * 2^k ]</strong>, for <strong>k</strong> in <strong>[1,64]</strong>, which is <strong>64</strong> queries.</p> <p>So, to sum up, the <strong><em>average</em></strong> <code>minmod(m)</code> query complexity will be <strong>O(64*logn)</strong>. In general, if we <strong>m</strong> has unknown upper bound, this will be <strong>O(logm<em>logn)</strong>. The BST update is, as known, <strong>O(logn)</strong>, so the overall complexity in case of <strong>n</strong> queries will be <strong>O(n</em>logm*logn)</strong>.</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