3

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.

R B
  • 9,448
  • 5
  • 34
  • 74
  • 1
    This can implement the sliding window median, which would get you the desired lower bound. http://cstheory.stackexchange.com/a/21736/314 – Chao Xu Feb 02 '16 at 12:03
  • @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 Feb 02 '16 at 12:09
  • Specifically, any $\omega(1)$ lower bound, without any assumptions on the way it works, would be interesting. – R B Feb 02 '16 at 12:10
  • 1
    Are the values v assumed to be bounded? ​ ​ –  Feb 02 '16 at 14:30
  • @RickyDemer - no. – R B Feb 02 '16 at 14:34
  • In that case, there should be a straight-forward $\Omega \hspace{.02 in}(\hspace{.02 in}\log(v))$ lower bound - When the first 2 Set operations are to v with distinct ks, and the next ceil(n/2)-1 are to something larger than v, a subsequent Median operation must return v, so at least 1/2 of v's bits must have been read during at least one of the first 2 Set operations. ​ ​ ​ –  Feb 02 '16 at 14:39
  • @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 Feb 02 '16 at 14:45
  • Are the values v assumed to satisfy ​ |v| ≤ poly(n) ? ​ ​ ​ That would determine whether this is on a word RAM or a transdichotomous machine. ​ ​ ​ ​ ​ ​ ​ ​ –  Feb 02 '16 at 14:50
  • 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. – Jukka Suomela Feb 02 '16 at 20:09
  • 2
    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 Feb 03 '16 at 20:32

0 Answers0