5
$\begingroup$

We are given an (unsorted) list $L=(a_1,\dots,a_n)$ of numbers of size $n$, where $a_i\in \{ 1,\dots,B\}$.

We want to find the minimum number $x$ from $\{ 1,\dots,B\} \backslash L$.

What is the space complexity of this problem ? (The space to store the input, $L$, does not count.) What if the input $L$ is in a stream which you can only read from left to right for at most constant number of passes ?

The obvious way to solve this is just to copy $L$ into the working memory and then (in-place) sort $L$, and find $x$ in the obvious way. This algorithm uses space of size $n$.

Can we do better ?

$\endgroup$
  • $\begingroup$ Is this a homework exercise? This sounds like a communication complexity lower bound. $\endgroup$ – Yuval Filmus Apr 9 '13 at 23:42
  • $\begingroup$ It is not a homework. It is just a question popping up, when I was trying to learn sublinear algorithms. $\endgroup$ – eig Apr 9 '13 at 23:46
4
$\begingroup$

You can solve this in time $O(n\log B)$ and constant space (assuming a machine word can store numbers up to $\max(n,B)$) using binary search.

Edit: Here are some more details. I am making the assumption that no number appears twice - perhaps that's an unfounded assumption. Given $K$, we can check whether $K<L$, $K=L$ or $K>L$ by counting how many numbers smaller than $K$ appear in the input, and whether $K$ itself appears in the input. This takes $O(n)$.

Edit 2: Following eig's suggestion, since we know that the missing number is smaller than $n+2$, this actually takes time $O(n\log n)$.

$\endgroup$
  • $\begingroup$ Thank you. But sorry, I think I need to adjust my question a little bit. My intention was that it is allowed to read the input for at most constant number of passes. $\endgroup$ – eig Apr 9 '13 at 23:33
  • $\begingroup$ Even if there is no constraint about how we can read the input, I still don't see how to do it in $O(n \log B)$ time. Could you please specify more how to achieve this? $\endgroup$ – eig Apr 11 '13 at 10:41
  • 1
    $\begingroup$ You're right, I'm making the assumption that $L$ contains no repeated numbers. $\endgroup$ – Yuval Filmus Apr 11 '13 at 13:03
  • 2
    $\begingroup$ Assuming that the numbers are distinct, (we have that $B \ge n$), but then we can improve the time a little bit to $O(n \log n)$ because we know the missing number $x \in [1,n]$ $\endgroup$ – eig Apr 15 '13 at 14:17
3
$\begingroup$

For your second question, one can obtain some space bounds for deterministic streaming. (See Sasho Nikolov's answer for the randomized single-pass case.)

If $n$ is constant, you can find the minimum using $\lceil \log_2 B \rceil$ bits, by storing the smallest element not seen so far, and streaming the list $n$ times. Each pass is guaranteed to either result in the minimum, or to disqualify one (or more, if there are repeats) of the $n$ elements of the list.

I presume you actually meant that $n$ should not be fixed.

Then with single-pass deterministic streaming, one has to use at least $B$ bits of space. This is required to distinguish the different choices of the list $L$, by an application of the single-pass streaming Comparison Lemma (see ECCC TR12-183 for details about the technique). The intuition is that if fewer bits are kept, then there are two input streams that represent two different subsets of $B$ which end up with the same internal state; an adversary can then add numbers to the end of the stream to ensure that the algorithm gives the wrong answer. For an upper bound, $B + 2\lceil \log B \rceil$ bits is enough. Keep an array of $B$ bits, a variable to index to the array, and a temporary variable. Initially the array entries are set to 0. Change the bit for $i$ to 1 if $i$ is read. The first 0 entry in the array gives the right answer. So the lower bound of $B$ bits is nearly tight for single-pass deterministic streaming.

I have not seen this problem before, and I do not know what the bounds would be for more than 1 but less than $n$ passes. See also a similar question of mine at CSTheory.

Edit: expanded and corrected the single-pass bounds.

$\endgroup$
  • $\begingroup$ Unlike the randomized case, in the deterministic case the multiplicative constant is $1$ for the lower bound, and arbitrarily close to $1$ for the upper bound. $\endgroup$ – András Salamon Apr 15 '13 at 17:33
2
$\begingroup$

An easy reduction from the Index problem shows a lower bound of $\Omega(B)$ for single pass randomized algorithms. Recall that in the Index problem Alice is given a subset $S$ of $U$ and Bob is given an element $e$ of $U$. The goal is to compute whether $e \in S$. The (randomized) one-way communication complexity of Index is $\Omega(|U|)$.

For the reduction, let us identify $U$ with $\{1, \ldots, B\}$, i.e. fix some bijection $f$ between $U$ and $\{1, \ldots, B\}$. For an instance $(S, e)$ of the Index problem, let $L_0 = \{1, \ldots, B\} \setminus f(S)$, where $f(S) = \{f(a): a \in S\}$; let $L_1 = \{i: i < f(e)\}$. The stream consists of $L_0$ followed by $L_1$. Clearly the minimum number not in $L = L_0 \cup L_1$ is at least $f(e)$, because $L_1$ includes all numbers smaller than $f(e)$. If $e \in S$, then $L_0$ does not include $f(e)$ and the minimum number outside $L$ is at least $f(e) + 1$; otherwise the minimum is $f(e)$.

As usual, Alice can process $L_0$ using the streaming algorithm, send the contents of memory to Bob, who then uses the memory to process $L_1$ and compute the final answer and decide whether $f \in S$. This gives a one-way communication protocol for Index with communication complexity at most the space complexity of the streaming protocol, and, because the communication complexity is at least $\Omega(|U|) = \Omega(B)$, the space complexity is at least as many bits as well. Obviously this is tight up to constants for single-pass streaming.

$\endgroup$
1
$\begingroup$

Suppose instead that you're interested in the parity of $x$. Consider the two-player communication scenario where one player gets the even half of $L$ and the other player gets the odd half of $L$. It seems plausible that the deterministic communication complexity of this game is $\Omega(n)$, and so the usual argument would give an $\Omega(n)$ bits space lower bound.

$\endgroup$
  • $\begingroup$ For more on this argument, the appropriate catch phrases are "streaming algorithms" and "communication complexity lower bounds". $\endgroup$ – Yuval Filmus Apr 10 '13 at 0:09
  • $\begingroup$ This depends entirely on whether the parties are allowed to have any bits in common. $\endgroup$ – András Salamon Apr 17 '13 at 2:50
  • $\begingroup$ Since we want to get the strongest possible bound, we won't allow them to have any bits in common. $\endgroup$ – Yuval Filmus Apr 17 '13 at 2:52
  • $\begingroup$ If the parties know that they have no bits in common, then Parity only requires two bits of communication: the first party computes the parity of its inputs, sends it to the second party, who then computes the parity of its inputs together with the first party's parity bit, and sends the result to the first party. $\endgroup$ – András Salamon Apr 17 '13 at 12:48
  • $\begingroup$ I don't follow. Player 1 gets for every even number $2n$ whether $2n \in L$. Player 2 gets for every odd number $2n+1$ whether $2n+1 \in L$. Their goal is to find out the minimum missing number. What is the relevance of the parity of the inputs? $\endgroup$ – Yuval Filmus Apr 17 '13 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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