3
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ This can implement the sliding window median, which would get you the desired lower bound. cstheory.stackexchange.com/a/21736/314 $\endgroup$
    – Chao Xu
    Feb 2, 2016 at 12:03
  • $\begingroup$ @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? $\endgroup$
    – R B
    Feb 2, 2016 at 12:09
  • 1
    $\begingroup$ Are the values v assumed to be bounded? ​ ​ $\endgroup$
    – user6973
    Feb 2, 2016 at 14:30
  • 2
    $\begingroup$ @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. $\endgroup$
    – Jukka Suomela
    Feb 2, 2016 at 20:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – greg
    Feb 3, 2016 at 20:32

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.