<p>The question's title presupposes the wrong answer.  Median can in fact be maintained in <span class="math-container">$O(1)$</span> time.  Here is the counter example disproving the title's fallacious claim of “How to show that the median cannot be maintained in <span class="math-container">$O(1)$</span> time?”.</p>
<p>The given problem-statement demands that time-growth be <span class="math-container">$O(1)$</span> but does not regulate space-growth.  Hence space growth can be anything that we desire to pull off an <span class="math-container">$O(1)$</span> growth rate, but therein lies the rub:  the maintenance of the <span class="math-container">$O(—)$</span> growth rate for size of space must itself be <span class="math-container">$O(1)$</span> too (where <span class="math-container">$—$</span> 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.  <span class="math-container">$O(1)$</span> tracking of median hence means <span class="math-container">$O(n)$</span> calculation of median for the population n, when viewed as the final result cumulatively instead of incrementally.</p>
<p>One of the most ingenious <span class="math-container">$O(1)$</span>-time data structures is the radix trie for a given <span class="math-container">$log_{2}(max(X))$</span>, where <span class="math-container">$max(X)$</span> is the maximum potential value of any <span class="math-container">$x_{i}∈X$</span> in the population of size <span class="math-container">$n_{∞}$</span>.  Note that <span class="math-container">$log_{2}(max(X))$</span> [i.e., the word size, say, 32-bit integers &amp; hence the radix-tree rate of growth] in no way depends on <span class="math-container">$log_{2}(n_{∞})$</span>, say, 64-bit integers/pointers.  Or in other words, each insertion and access of the <span class="math-container">$k$</span>-ary radix trie is an <span class="math-container">$O(1)$</span> operation for each incremental expansion of the population size, which matches our goal for an <span class="math-container">$O(1)$</span> 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 <span class="math-container">$O(1)$</span> 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 <span class="math-container">$k$</span> is binary=2, but this data structure and its algorithm extrapolates nicely to any integer radix <span class="math-container">$k≥2$</span> as well; this higher-radix extrapolation of this answer will be elided for brevity.</p>
<p><strong>Clever threadedness in the radix trie</strong>
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 <span class="math-container">$O(1)$</span> insertion of that leaf as a by-product of this access) is an <span class="math-container">$O(log_{2}(max(X)))$</span> operation to traverse all the bits within each <span class="math-container">$xi$</span>.  Note that <span class="math-container">$log_{2}(max(X))$</span> is a constant (e.g., 64 on modern computers for 64-bit integers), hence <span class="math-container">$O(log_{2}(max(X)))$</span> in effect simplifies to <span class="math-container">$O(1)$</span> in Bachmann–Landau notation because <span class="math-container">$n$</span> is constant at engineering-time of the design of the software by the choice of, say, 64-bit integers as the range of set <span class="math-container">$X$</span> for all <span class="math-container">$x_{i}∈X$</span>.  Insertion of a new leaf into the doubly-linked threaded list is also <span class="math-container">$O(1)$</span> because for each attempt to visit a leaf the immediate predecessor in bitwise value (i.e., <span class="math-container">$x_{i}-1$</span>) and immediate successor in bitwise value (i.e., <span class="math-container">$x_{i}+1$</span>) of each incoming <span class="math-container">$x_{i}$</span> is also attempted to visited, all of which are themselves <span class="math-container">$O(1)$</span> operations.</p>
<p><strong>Clever population-size partitioning in the radix trie</strong>
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 <span class="math-container">$log_{2}(max(X))$</span>-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 ≤<span class="math-container">$log_{2}(max(X))-1$</span> 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 <span class="math-container">$O(1)$</span> operation.</p>
<p><strong>Direct read-out of the median incrementally via 1 access of a leaf in a radix trie</strong>
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:</p>
<p><span class="math-container">$median(x_{i})≡\begin{cases}x_{\left\lfloor i+1\over 2\right\rfloor}&amp;\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}&amp;\text{|}\ \lfloor i/2\rfloor ≡ 0(mod 2)\end{cases}$</span></p>

CC BY-SA 4.0
2022-04-27T17:59:43.757Z
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.
Eli
CC BY-SA 4.0
2022-04-27T18:10:34.010Z
@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.
Andreas ZUERCHER
CC BY-SA 4.0
2022-04-27T18:21:32.753Z
@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.
Andreas ZUERCHER
CC BY-SA 4.0
2022-04-28T04:48:24.097Z
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).
Louis
CC BY-SA 4.0
2022-04-28T07:21:12.640Z
@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.
holf
CC BY-SA 4.0
2022-04-28T07:44:52.657Z
@Holf, I agree with you, you cannot maintain the median of an arbitrarily large set on a computer with finite memory. My answer was there to actually highlight this point: if you suppose a finite memory and push the reasoning to its limit (as I did in my example with a list of size 2^64), then everything falls apart in terms of complexity analysis.
Louis
CC BY-SA 4.0
2022-04-28T13:38:07.913Z
@Louis, if radix trie or PATRICIA trie is the beautiful round wheel invented in 1968, then van Emde Boas & his team reinvented an ugly square wheel in 1975 using vastly more complex operations such as square root & division instead of radie-trie's/PATRICIA-trie's simple bit manipulation.
Andreas ZUERCHER
CC BY-SA 4.0
2022-04-27T16:55:33.540Z
2022-04-27T18:17:43.830Z
2022-04-27T18:17:43.830Z
Andreas ZUERCHER
<p>If you can maintain the median of <span class="math-container">$n$</span> objects in <span class="math-container">$O(1)$</span>, then you can sort a sequence <span class="math-container">$x_1, \dots, x_n$</span> in <span class="math-container">$O(n)$</span>:</p>
<ul>
<li>first you compute a value <span class="math-container">$a$</span> smaller than all elements in the sequence and a value <span class="math-container">$b$</span> bigger than everything in the sequence;</li>
<li>then you build a structure giving you the median for the sequence <span class="math-container">$a, \dots, a, x_1, \dots, x_n$</span> where <span class="math-container">$a$</span> is present <span class="math-container">$n-1$</span> times. The median is thus the smallest element from your sequence then you repeat <span class="math-container">$2n$</span> times adding <span class="math-container">$b$</span> 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 <span class="math-container">$x_1, \dots, x_n$</span> in time <span class="math-container">$n\times T(3n)$</span> where <span class="math-container">$T(n)$</span> is the update time.</li>
</ul>
<p>All in all, if you suppose that your numbers can only be compared, then you have the <span class="math-container">$\Omega(ln(n))$</span> for maintenance because no sorting algorithm using only comparisons can go faster than <span class="math-container">$O(ln(n))$</span>.</p>
<p>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. <em>Equivalence between priority queues and sorting</em> from Thorup and <em>Integer Sorting in <span class="math-container">$O\left(n \sqrt{log(log(n))}\right)$</span> Expected Time and Linear Space</em> from Han and Thorup.</p>
<p>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  <span class="math-container">$O\left(\sqrt{ln(ln(n))}\right)$</span> randomized upper bound, a <span class="math-container">$O(ln(ln(n)))$</span> deterministic one but no lower bound above <span class="math-container">$\Omega(1)$</span>…</p>

CC BY-SA 4.0
2022-04-27T18:27:15.700Z
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.
Andreas ZUERCHER
CC BY-SA 4.0
2022-04-28T04:36:15.360Z
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).
Louis
CC BY-SA 4.0
2022-04-28T06:53:16.303Z
@Louis - do you know if any of these algorithms translate to efficient solutions to my problem (assuming $O(\log n)$ bit integers)?
Eli
CC BY-SA 4.0
2022-04-28T07:02:41.920Z
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.
Louis
CC BY-SA 4.0
2022-04-27T16:19:46.913Z
2022-04-27T16:19:46.913Z
Louis
<p>Suppose that we have a stream of numbers <span class="math-container">$x_1,x_2,\ldots$</span> such that we wish to track the median of the values observed so far.</p>
<p>This task is easy to do with <span class="math-container">$O(\log n)$</span> update time (where <span class="math-container">$n$</span> is the current number of elements), giving <span class="math-container">$O(n\log n)$</span> computation in total, compared with <span class="math-container">$O(n)$</span> that is needed if we received all elements at once.</p>
<blockquote>
<p><strong>Is it provably impossible to track the streaming median in <span class="math-container">$O(1)$</span> time?</strong></p>
</blockquote>
<hr />
<p>Edit: I'm familiar with some median approximation algorithms, but I'm interested in the exact median.</p>

CC BY-SA 4.0
2022-04-27T16:02:18.217Z
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?
Jake
CC BY-SA 4.0
2022-04-27T18:00:22.353Z
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$).
Eli
CC BY-SA 4.0
2022-04-27T20:14:42.860Z
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.
Neal Young
CC BY-SA 4.0
2022-04-28T06:13:25.487Z
@NealYoung, sure, we can assume $O(\log \overline n)$ bits integers. Thanks for your interest.
Eli
<ds.algorithms><ds.data-structures><data-streams><streaming-algorithms><streaming>
How to show that the median cannot be maintained in $O(1)$ time?
Eli
# How to show that the median cannot be maintained in $O(1)$ time?

(Asked by: username_0 on 2022-04-27)

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.

**Tags:** ds.algorithms, ds.data-structures, data-streams, streaming-algorithms, streaming
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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$).  
> **username_2**: 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.  
> **username_0**: @NealYoung, sure, we can assume $O(\log \overline n)$ bits integers. Thanks for your interest.  

---

## 2 answers

### Answer by username_4 on 2022-04-27. Score: 11 | Accepted answer

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)$…

> **Comments:**
> **username_3**: 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.  
> **username_4**: 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).  
> **username_0**: @Louis - do you know if any of these algorithms translate to efficient solutions to my problem (assuming $O(\log n)$ bit integers)?  
> **username_4**: 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.  

---

### Answer by username_3 on 2022-04-27. Score: 0

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}$

> **Comments:**
> **username_0**: 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.  
> **username_3**: @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.  
> **username_3**: @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.  
> **username_4**: 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).  
> **username_5**: @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.  
> **username_4**: @Holf, I agree with you, you cannot maintain the median of an arbitrarily large set on a computer with finite memory. My answer was there to actually highlight this point: if you suppose a finite memory and push the reasoning to its limit (as I did in my example with a list of size 2^64), then everything falls apart in terms of complexity analysis.  
> **username_3**: @Louis, if radix trie or PATRICIA trie is the beautiful round wheel invented in 1968, then van Emde Boas & his team reinvented an ugly square wheel in 1975 using vastly more complex operations such as square root & division instead of radie-trie's/PATRICIA-trie's simple bit manipulation.  

---

