Median Algorithm in O(log n)

Question

How can we remove the median of a set with time complexity O(log n)? Some idea?

Answer 1

If the set is sorted, finding the median is O(1). If not, how is one supposed to determine the median of a set without looking at all of the numbers at least once?

Answer 2

For unsorted lists, repeatedly do O(n) partial sort until the element located at the median position is known. This is at least O(n), though.

Is there any information about the elements being sorted?

Answer 3

For a general, unsorted set, it is impossible to reliably find the median in better than O(n) time. You can find the median of a sorted set in O(1), or you can trivially sort the set yourself in O(n log n) time and then find the median in O(1), giving an O(n logn n) algorithm. Or, finally, there are more clever median selection algorithms that can work by partitioning instead of sorting and yield O(n) performance.

But if the set has no special properties and you are not allowed any pre-processing step, you will never get below O(n) by the simple fact that you will need to examine all of the elements at least once to ensure that your median is correct.

Answer 4

Here's a solution in Java, based on TreeSet:

public class SetWithMedian {
    private SortedSet<Integer> s = new TreeSet<Integer>();
    private Integer m = null;

    public boolean contains(int e) {
        return s.contains(e);
    }
    public Integer getMedian() {
        return m;
    }
    public void add(int e) {
        s.add(e);
        updateMedian();
    }
    public void remove(int e) {
        s.remove(e);
        updateMedian();
    }
    private void updateMedian() {
        if (s.size() == 0) {
            m = null;
        } else if (s.size() == 1) {
            m = s.first();
        } else {
            SortedSet<Integer> h = s.headSet(m);
            SortedSet<Integer> t = s.tailSet(m + 1);
            int x = 1 - s.size() % 2;
            if (h.size() < t.size() + x)
                m = t.first();
            else if (h.size() > t.size() + x)
                m = h.last();
        }
    }
}

Removing the median (i.e. "s.remove(s.getMedian())") takes O(log n) time.

Edit: To help understand the code, here's the invariant condition of the class attributes:

private boolean isGood() {
    if (s.isEmpty()) {
        return m == null;
    } else {
        return s.contains(m) && s.headSet(m).size() + s.size() % 2 == s.tailSet(m).size();
    }
}

In human-readable form:

• If the set "s" is empty, then "m" must be null.
• If the set "s" is not empty, then it must contain "m".
• Let x be the number of elements strictly less than "m", and let y be the number of elements greater than or equal "m". Then, if the total number of elements is even, x must be equal to y; otherwise, x+1 must be equal to y.

Answer 5

I know one randomize algorithm with time complexity of O(log n) in expectation.

Here is the algorithm:

Input: array of n numbers A[1...n] [without loss of generality we can assume n is even]

Output: n/2th element in the sorted array.

Algorithm ( A[1..n] , k = n/2):

Pick a pivot - p universally at random from 1...n

Divided array into 2 parts:

L - having element <= A[p]

R - having element > A[p]

if(n/2 == |L|) A[|L| + 1] is the median stop

if( n/2 < |L|) re-curse on (L, k)

else re-curse on (R, k - (|L| + 1)

Complexity: O( log n) proof is all mathematical. One page long. If you are interested ping me.