6
$\begingroup$

Suppose that we have a stream of numbers $x_1,x_2,\ldots$ such that we wish to track the median of the values observed so far.

This task is easy to do with $O(\log n)$ update time (where $n$ is the current number of elements), giving $O(n\log n)$ computation in total, compared with $O(n)$ that is needed if we received all elements at once.

Is it provably impossible to track the streaming median in $O(1)$ time?


Edit: I'm familiar with some median approximation algorithms, but I'm interested in the exact median.

$\endgroup$
4
  • $\begingroup$ Is the length of the numbers included in the runtime analysis? E.g. a Turing machine cannot compare two numbers in constant time. Or are you assuming a machine model with registers that can add/compare numbers in constant time? And if so, what specific model are you assuming? $\endgroup$
    – Jake
    Apr 27 at 16:02
  • $\begingroup$ Hi Jake. Thanks for the comment. Let us assume the standard word RAM with $O(\log\overline n)$-sized words (where $\overline n$ is an upper bound on $n$). $\endgroup$
    – Eli
    Apr 27 at 18:00
  • $\begingroup$ What do you assume about the numbers $x_i$? Are they integers? $O(\log n)$ bits each? The question seems interesting in a comparison-only model. $\endgroup$
    – Neal Young
    Apr 27 at 20:14
  • $\begingroup$ @NealYoung, sure, we can assume $O(\log \overline n)$ bits integers. Thanks for your interest. $\endgroup$
    – Eli
    Apr 28 at 6:13

2 Answers 2

11
$\begingroup$

If you can maintain the median of $n$ objects in $O(1)$, then you can sort a sequence $x_1, \dots, x_n$ in $O(n)$:

  • first you compute a value $a$ smaller than all elements in the sequence and a value $b$ bigger than everything in the sequence;
  • then you build a structure giving you the median for the sequence $a, \dots, a, x_1, \dots, x_n$ where $a$ is present $n-1$ times. The median is thus the smallest element from your sequence then you repeat $2n$ times adding $b$ and every two add, the median changes and gives you the next element in order. From this, you get a sorting algorithm for the sequence $x_1, \dots, x_n$ in time $n\times T(3n)$ where $T(n)$ is the update time.

All in all, if you suppose that your numbers can only be compared, then you have the $\Omega(ln(n))$ for maintenance because no sorting algorithm using only comparisons can go faster than $O(ln(n))$.

That being said, if you allow faster sorting algorithms (because you have integers or floating point numbers with a limited precision) then you can maintain the median using a fast priority queue. See e.g. Equivalence between priority queues and sorting from Thorup and Integer Sorting in $O\left(n \sqrt{log(log(n))}\right)$ Expected Time and Linear Space from Han and Thorup.

Any progress on your problem (upper or lower bound) would translate to a progress on sorting, which would be quite interesting! At the moment, to the best of my knowledge, we have a $O\left(\sqrt{ln(ln(n))}\right)$ randomized upper bound, a $O(ln(ln(n)))$ deterministic one but no lower bound above $\Omega(1)$

$\endgroup$
4
  • $\begingroup$ See my other answer for demonstration that no sort is required per additional element of the sequence by not depending on a priority-queue whatsoever. The other answer depends on the value of the binary numeral already being sorted by its bit value; hence no additional sorting step is required. Simply use the already-sorted valuation of the •number• in its binary •numeral• form. O(1) solution utilizes a sorting that has already been performed by prior number-to-numeral conversion, so no more sorting is necessary. Hence, your entire reasoning based on sorting collapses as superfluous. $\endgroup$ Apr 27 at 18:27
  • 2
    $\begingroup$ Hello, I am not saying that any algorithm for the median has to use explicitly a sort or a priority queue, I am saying that they are equivalent problems and therefore any datastructure for median maintenance can be turned into a sort and conversely that any sort can be turned into a median maintenance scheme. I don't fully understand your answer but, still, if you provide me with a program implementing it, I can turn it into a sort (as explained in my answer above). $\endgroup$
    – Louis
    Apr 28 at 4:36
  • $\begingroup$ @Louis - do you know if any of these algorithms translate to efficient solutions to my problem (assuming $O(\log n)$ bit integers)? $\endgroup$
    – Eli
    Apr 28 at 6:53
  • $\begingroup$ If you mean "theoretically" efficient then yes, they all work with $O(\log(n))$ integers. Now if you mean in practice, well, that will depend on your $n$ and on the shape of data but a van Emde Boas tree is pretty efficient. Also for a real world application you might want to take into account the distribution of data. $\endgroup$
    – Louis
    Apr 28 at 7:02
0
$\begingroup$

The question's title presupposes the wrong answer. Median can in fact be maintained in $O(1)$ time. Here is the counter example disproving the title's fallacious claim of “How to show that the median cannot be maintained in $O(1)$ time?”.

The given problem-statement demands that time-growth be $O(1)$ but does not regulate space-growth. Hence space growth can be anything that we desire to pull off an $O(1)$ growth rate, but therein lies the rub: the maintenance of the $O(—)$ growth rate for size of space must itself be $O(1)$ too (where $—$ is mnemonic for: whatever it may be), since incremental maintenance of whatever data struture is utilized to incrementally calculate median is itself a proper suboperation within the calculation of median. The definition of “track” here is important: the word “track” here refers to a single incremental expansion of the population size by one member. $O(1)$ tracking of median hence means $O(n)$ calculation of median for the population n, when viewed as the final result cumulatively instead of incrementally.

One of the most ingenious $O(1)$-time data structures is the radix trie for a given $log_{2}(max(X))$, where $max(X)$ is the maximum potential value of any $x_{i}∈X$ in the population of size $n_{∞}$. Note that $log_{2}(max(X))$ [i.e., the word size, say, 32-bit integers & hence the radix-tree rate of growth] in no way depends on $log_{2}(n_{∞})$, say, 64-bit integers/pointers. Or in other words, each insertion and access of the $k$-ary radix trie is an $O(1)$ operation for each incremental expansion of the population size, which matches our goal for an $O(1)$ incremental calculation of median. Now, we need just the right clever threadedness of the leaves of the radix trie to be useful to direct inspection of the median. Also we need just the right clever count of divided population size at each leg of each branch of the radix trie so that we know by simple inspection at time of $O(1)$ access of the radix trie how many members of the population are along subordinate branches of the radix trie. Conceptually, this is easiest to envision when the radix $k$ is binary=2, but this data structure and its algorithm extrapolates nicely to any integer radix $k≥2$ as well; this higher-radix extrapolation of this answer will be elided for brevity.

Clever threadedness in the radix trie The leaves of the radix trie shall be a doubly-linked list. This is done so that the successor direction of that doubly-linked list states the ascending order of the population even if that population arrived incrementally out-of-order (or even if that population arrived incrementally in any particular order, such as descending, or partially ordered). A single access of a leaf in the radix trie (which might or might not have been an $O(1)$ insertion of that leaf as a by-product of this access) is an $O(log_{2}(max(X)))$ operation to traverse all the bits within each $xi$. Note that $log_{2}(max(X))$ is a constant (e.g., 64 on modern computers for 64-bit integers), hence $O(log_{2}(max(X)))$ in effect simplifies to $O(1)$ in Bachmann–Landau notation because $n$ is constant at engineering-time of the design of the software by the choice of, say, 64-bit integers as the range of set $X$ for all $x_{i}∈X$. Insertion of a new leaf into the doubly-linked threaded list is also $O(1)$ because for each attempt to visit a leaf the immediate predecessor in bitwise value (i.e., $x_{i}-1$) and immediate successor in bitwise value (i.e., $x_{i}+1$) of each incoming $x_{i}$ is also attempted to visited, all of which are themselves $O(1)$ operations.

Clever population-size partitioning in the radix trie Each branch of the radix trie shall contain the number of subordinate leaves along the leftward (i.e., 0-bit) branch and the number of subordinate leaves along the rightward (i.e., 1-bit) branch. An $log_{2}(max(X))$-sized array of pointers of traversed branches from root to leaf is always maintained for each attempt to access a leaf (which might imply an insertion of a leaf). Upon insertion, all elements of this array are visited to update their left-/0-subordinate count and their right-/1-subordinate count. Because ≤$log_{2}(max(X))-1$ nonleaf nodes in the radix trie are always accessed for this fixed-size maintenance for each insertion, this refresh of these counts along that root-to-leaf walk is itself an $O(1)$ operation.

Direct read-out of the median incrementally via 1 access of a leaf in a radix trie From the ascending order of the treadedness of the leaves, and from the partitioning of the population size at each nonleaf node in the radix trie, the following standard definitions of median can be directly utilized:

$median(x_{i})≡\begin{cases}x_{\left\lfloor i+1\over 2\right\rfloor}&\text{|}\ \lfloor i/2\rfloor ≡ 1(mod 2)\\ \\{x_{\left\lfloor \frac{i}{2}\right\rfloor} + x_{\left\lfloor \frac{i}{2}\right\rfloor+1}\over 2}&\text{|}\ \lfloor i/2\rfloor ≡ 0(mod 2)\end{cases}$

$\endgroup$
7
  • $\begingroup$ Hi Andreas. Thanks for the answer. This may be an engineering solution, but if we assume the standard word RAM with $O(\log\overline n)$-sized words (where $\overline n$ is an upper bound on $n$) then $\log$ is not a constant and I don't think that the solution (which I couldn't fully follow) qualifies as $O(1)$ update time. $\endgroup$
    – Eli
    Apr 27 at 17:59
  • $\begingroup$ @Eli, in practice, the size of 64-bit integers is in fact constant and quite large enough to handle the vast vast majority of problem spaces. Take my answer as proof then that $O(log_{2}(max(X)))$ is the lowest big-omicron when not only the population size increases, but also the range of X where the problem's $x_{i}∈X$. Dynamically ever larger range of values $x_{i}$ was not given in the problem statement, only ever-larger population sizes, on which this answer does not depend. $\endgroup$ Apr 27 at 18:10
  • $\begingroup$ @Eli, to drive my point home, I updated my answer to divorce the word sizes of the maximum value of each $x_{i}$, say, 32-bit from the word size of the maximum population size of $n_{∞}$, say, 256-bit. Your comment above is interestingly correct only if $max(x_{i})$ is allowed to grow arbitrarily large (not implied whatsoever by the wording of your question as stated), not if $n_{∞}$ is allowed to grow arbitrarily large, as implied by the wording of your question as stated. Methinks the rules of your game are changing midgame. $\endgroup$ Apr 27 at 18:21
  • $\begingroup$ Not to discard your answer but I think the problem was implicitly framed within the setting of the transdichotomous RAM model. Note that if you suppose that the integers are bounded by 64 bits, then simply maintaining a list of elements plus the number of times they appear and recomputing the median would also be O(1) since that list is bounded by the constant 2^64. More practically, a van Emde Boas tree would also be O(1) but with a constant "proportional" to log(64). $\endgroup$
    – Louis
    Apr 28 at 4:48
  • $\begingroup$ @Louis: How would you maintain the counters for each value? They may grow arbitrarily big and you will not be able to do arithmetic operations on it in constant time (though you can manipulate approximation using the last bit of a Gray code encoding, but I do not think it is enough to compute maintain the median. $\endgroup$
    – holf
    Apr 28 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.