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
You may assume that the array is initialized to zeros, and you can preprocessing to initialize any data structure you want.
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.