<p>Consider the problem of needing to support an $n$ integers array structure with two operations:</p>

<ul>
<li>Set(k,v) - set the $k$'th integer to value $v$ (i.e. $A[k]=v$).</li>
<li>Median() - return the median value of the array.</li>
</ul>

<p>Suppose that the median functionality has to run in $O(1)$ time.</p>

<blockquote>
  <p><strong>What is the complexity of the <code>set</code> operation</strong>?</p>
</blockquote>

<hr>

<p>You may assume that the array is initialized to zeros, and you can preprocessing to initialize any data structure you want.</p>

<hr>

<p>Implementing <code>set</code> in $O(\log n)$ time is straightforward. 
I'm specifically interested in showing a lower bound.</p>

<hr>

<p>The special case in which the <code>set</code> function may only increase the value of an element is also of interest.</p>

CC BY-SA 3.0
2016-02-02T12:03:19.677Z
This can implement the sliding window median, which would get you the desired lower bound. http://cstheory.stackexchange.com/a/21736/314
Chao Xu
CC BY-SA 3.0
2016-02-02T12:09:35.547Z
@ChaoXu - thanks, this doesn't quite give me the lower bound, as the implementation of this array might not be comparison based. Also, I believe that David's answer requires to know the entire input in advance, right?
R B
CC BY-SA 3.0
2016-02-02T12:10:38.557Z
Specifically, any $\omega(1)$ lower bound, without any assumptions on the way it works, would be interesting.
R B
CC BY-SA 3.0
2016-02-02T14:34:02.423Z
@RickyDemer - no.
R B
CC BY-SA 3.0
2016-02-02T14:45:29.520Z
@RickyDemer - I see your point. Then I guess we can assume we are in a model where values and keys are represented using $O(1)$ memory words (otherwise this really makes no sense).
R B
CC BY-SA 3.0
2016-02-02T20:09:12.803Z
@RB: You get the lower bound "it is at least as hard as sorting", so there is a nontrivial lower bound unless you happen to have a setting in which sorting can be done in linear time.
Jukka Suomela
CC BY-SA 3.0
2016-02-03T20:32:25.397Z
I doubt that you can find a better bound than the one given by @JukkaSuomela, because any implementation of a min-heap that supports the min operation in time O(1) and the set operation in time f(n) would also an imply a solution to your problem where the set operation takes time f(n). This is using the undergrad implementation of a median-heap using two min-heaps. Thus, the complexity of median-heap and min-heap are the same, and IIRC Thorup has a paper that shows that the complexity of min-heap is tightly related to the complexity of sorting.
greg
<ds.algorithms><lower-bounds><data-streams><streaming-algorithms>
Finding median in a changing array
R B
# Finding median in a changing array

(Asked by: username_0 on 2016-02-02)

Consider the problem of needing to support an $n$ integers array structure with two operations:

* Set(k,v) - set the $k$'th integer to value $v$ (i.e. $A[k]=v$).
* Median() - return the median value of the array.

Suppose that the median functionality has to run in $O(1)$ time.

> **What is the complexity of the `set` operation**?

---

You may assume that the array is initialized to zeros, and you can preprocessing to initialize any data structure you want.

---

Implementing `set` in $O(\log n)$ time is straightforward.
I'm specifically interested in showing a lower bound.

---

The special case in which the `set` function may only increase the value of an element is also of interest.

**Tags:** ds.algorithms, lower-bounds, data-streams, streaming-algorithms
> **Comments:**
> **username_1**: This can implement the sliding window median, which would get you the desired lower bound. http://cstheory.stackexchange.com/a/21736/314  
> **username_0**: @ChaoXu - thanks, this doesn't quite give me the lower bound, as the implementation of this array might not be comparison based. Also, I believe that David's answer requires to know the entire input in advance, right?  
> **username_0**: Specifically, any $\omega(1)$ lower bound, without any assumptions on the way it works, would be interesting.  
> **username_0**: @RickyDemer - no.  
> **username_0**: @RickyDemer - I see your point. Then I guess we can assume we are in a model where values and keys are represented using $O(1)$ memory words (otherwise this really makes no sense).  
> **username_2**: @RB: You get the lower bound "it is at least as hard as sorting", so there is a nontrivial lower bound unless you happen to have a setting in which sorting can be done in linear time.  
> **username_3**: I doubt that you can find a better bound than the one given by @JukkaSuomela, because any implementation of a min-heap that supports the min operation in time O(1) and the set operation in time f(n) would also an imply a solution to your problem where the set operation takes time f(n). This is using the undergrad implementation of a median-heap using two min-heaps. Thus, the complexity of median-heap and min-heap are the same, and IIRC Thorup has a paper that shows that the complexity of min-heap is tightly related to the complexity of sorting.  

---

## 0 answers

