2
$\begingroup$

Given an integer $n$ and a tree set $S$, I would like to find the approximate median $x$ of the integer set $T := \{i \in \mathbb N : i < n \wedge i \notin S\}$. There are no constraints to the distribution of $S$, so it is not possible to assume that $S$ is uniformly distributed over $(0,n)$. This problem can be found in linear time with this algorithm:

def find_median(n, S):
    counter = 0
    for i in range(n):
        if i not in S:
            counter += 1
            if counter * 2 >= n - len(S):
                return i
    panic("n is smaller than len(S)")

I would define "approximate median" as follows:

Let $k$ be the index of $x$ in $T$. Then $\left|\frac{|T|}2-k\right| \in O(\log n)$.

If anyone is interested in my original goal: I wanted to bisect a set of tasks (where $S$ is the set of tasks I don't need to execute) to two workers, so I wish to find the splitting point, where off by a few elements is acceptable compared to the scope of the whole task set.

To illustrate with an example, for $n=11$ and $S=\{6,7,8,9,10\}$, we have $T = \{1,2,3,4,5\}$, so the median is $3$. We cannot simply find this by taking $\frac n2$ because $S$ may be biased.

The opposite of this problem (where $i \in S$ instead of $i \notin S$) can be trivially found in $O(\log n)$ time by finding the $\frac{|S|}2$th vertex in the tree set; even in tree set implementations where the cardinality of each subtree is not stored, for a balanced B-tree, we are only off by $O(\log |S|)$ elements in the worst case by selecting the middle node in every vertex (for odd B-trees) or the leftmost vertex in the $\frac n2+1$th topmost subtree (for even B-trees).

So, is it possible to achieve the same time complexity for the $i \notin S$ case? Or is it possible to prove the lower bound of this algorithm? And if possible, is it possible to achieve an ideal time complexity by just storing $O(\log |S|)$ extra metadata (e.g. on the $S$ tree set itself)?

$\endgroup$
10
  • 1
    $\begingroup$ You can do this it using binary search: for the current candidate $x$, the predicate is "the number of points in $T$ that are less than $x$ is at least $\frac{|T|}{2}$" (you can use binary search since this predicate is false to the left of the median, and true to the right of the median). To check this predicate, it suffices to find how many elements in $S$ are less than $x$, and you described how to do this. (BTW, what's wrong with linear time? Since your elements are tasks, they will require $O(1)$ time each. Also, you can maintain the median when you construct the tree for $S$) $\endgroup$
    – Dmitry
    Commented Nov 27, 2022 at 22:58
  • $\begingroup$ @Dmitry to answer your questions first: If the tasks are executed on different workers, let's say on multiple machines, $O(n)$ on a single task splitting machine may be unacceptable compared to each machine only processing $O\left(\frac n{|T|}\right)$ tasks. Furthermore, if the task itself is very lightweight, the cost of splitting may be comparable to the actual task, which would end up to be even slower than not splitting the tasks. $\endgroup$
    – SOFe
    Commented Nov 28, 2022 at 2:49
  • $\begingroup$ @SOFe, do I understand correctly that in your problem $T$ is not provided, only $n$ and $S$? $\endgroup$
    – Russel
    Commented Nov 28, 2022 at 2:52
  • $\begingroup$ @Dmitry yes, only $n$ and $S$. $n$ may get arbitrarily increased and $S$ may get arbitrarily inserted/removed with values less than the current $n$. I suppose maintaining the median is still possible this way although a bit troublesome. $\endgroup$
    – SOFe
    Commented Nov 28, 2022 at 2:54
  • 1
    $\begingroup$ @Russel I mean, how would you want to augment the tree? By storing extra data on the tree nodes or by modifying the tree implementation? Would be useful if there is a solution that way, but I am also interested in knowing its feasibility with only the basic inputs. $\endgroup$
    – SOFe
    Commented Nov 28, 2022 at 3:00

1 Answer 1

2
$\begingroup$

$T$ as the union of subintervals

Let $U = [1,n-1]$. In your problem, you can think of $S$ as elements removed from $U$. Removing an element splits $U$ into several smaller subintervals. The union of all these subintervals generates $T$.

Let $S' = S \cup \{0,n\}$. Working with $S'$ instead of $S$ will make some definitions more consistent and simpler.

Now assuming that elements of $S'$ are stored in a BST $S'_\tau$, then each node $y$ of the BST induces a left interval $L_y = [y_p+1,y-1]$ where $y_p$ is the predecessor of $y$ in $S'_\tau$. Note that since $0 \in S'_\tau$, all elements of $S$ have predecessors in $S'_\tau$.

The left intervals of all $y \in S'_\tau$ are exactly the subintervals that generates $T$.

Median Finding

The algorithm that will be described here is a modification of the order statistic tree.

First note that if we write down all the elements of $T$ in sorted order, the position of the median of $T$ in $T$ is $m = \left\lceil{\frac {n - |S|} 2}\right\rceil$.

Now, for each node $y \in S'_\tau$, let $size(y) = size(y_{l}) + size(y_{r}) + |L_y|$, where $y_{l}$ and $y_{r}$ are the left and right children of $y$, respectively, and $|L_{y}|$ is the size of the left interval of $y$. If $y_{l}$ does not exist then $size(y_{l}) = 0$. Similarly $size(y_{r}) = 0$, if $y_{r}$ does not exists.

Essentially, $size(y)$ gives the number of elements of $T$ in $y$'s subtree.

Let rank of $y$ be the number of elements of $T$ that is less than $y$.

To find the median, we first select $x$, the minimum node in $S'$ with rank greater than or equal to $m$.

  1. Initialize $y$ to be the root of $S'_\tau$ and $m' = m$.
  2. Let $r = size(y_l) + |L_y|$.
  3. If $r \ge m'$ and $size(y_l) \lt m'$ then $x = y$ and stop.
  4. Else if $r \ge m'$ and $size(y_l) \ge m'$, let $y = y_l$ and go to step 2.
  5. Otherwise, let $m' = m' - r$ and $y = y_r$ and go to step 2.

Once $x$ is found the median of $T$ is equal to $x_p + (m - size(x_l))$.

Notes

The algorithm can be implemented by augmenting a BST such that each node $y$ stores $size(y)$. This value can easily be updated in $O(1)$ time per node in the path during insert and delete. When the number of elements $n$ increases, it is also trivial to find node $n$ in the BST and update its value. It is assumed that $n$ is the initial element of the BST, prior to any insert.

If the BST is balanced the running-time of the median finding algorithm is $O(\log n)$.

$\endgroup$
1
  • 1
    $\begingroup$ Another way of thinking about this is that if you can use the size annotation to calculate the rank of an element, $\mathbf{rank}(x)$, then the rank of the complement set is $\mathbf{rank}'(x) = x - \mathbf{rank}(x)$. By the way, if you're storing the sizes of subtrees anyway, there's no reason not to use this information to balance the BST. See en.wikipedia.org/wiki/Weight-balanced_tree $\endgroup$
    – Pseudonym
    Commented Nov 30, 2022 at 4:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.