patternMinor
Find common min in logarithmic time
Viewed 0 times
logarithmictimeminfindcommon
Problem
I am looking for a data structure to store a set such that given two instances of size $O(n)$ which are known to have non-empty intersection, the minimum element of the intersection can be found in $O(\log n)$ time. Is this possible to achieve, either for worst-case or amortized complexity?
Other requirements for the data structure: $O(\log n)$ deletion, $O(n \log n)$ initialization.
Here is an example application of such a data structure, to clarify the requirements. The input consists of n subsets of $\{1, ..., n\}$ all containing the number n. The output is an n by n matrix whose $i, j$ entry is the minimal element in the intersection of sets i and j. With a basic approach one can solve this problem in $O(n^3)$ time. With a data structure satisfying the conditions above, one could solve it in $O(n^2 \log n)$ time.
Other requirements for the data structure: $O(\log n)$ deletion, $O(n \log n)$ initialization.
Here is an example application of such a data structure, to clarify the requirements. The input consists of n subsets of $\{1, ..., n\}$ all containing the number n. The output is an n by n matrix whose $i, j$ entry is the minimal element in the intersection of sets i and j. With a basic approach one can solve this problem in $O(n^3)$ time. With a data structure satisfying the conditions above, one could solve it in $O(n^2 \log n)$ time.
Solution
You can't. There is no such data structure. Assuming you have a separate instance per set, and each instance is initialized separately (using only information about the set it represents and not any information about any of the other sets), these running times are not achievable.
In particular, when you have two sets, finding the minimum common element takes $\Omega(n)$ time. Indeed, testing disjointness requires $\Omega(n)$ time, as explained here. Now, imagine starting with two sets $S_1,S_2$ over the universe $\{1,2,\dots,n-1\}$. Let $T_1=S_1 \cup \{n\}$ and $T_2 = S_2 \cup \{n\}$. Now $T_1,T_2$ are guaranteed to have a common element. So, if you had a good data structure for your problem, store $T_1$ in one instance of the data structure and $T_2$ in another. Then, if we had a way to find the minimum element of $T_1 \cap T_2$ in $o(n)$ time, this would give us a way to test disjointness of $S_1,S_2$ in $o(n)$ time (just test whether the minimum element is smaller than $n$) -- but we already know the latter is not possible. It follows that the former is not possible, either, i.e., any data structure for your problem must take $\Omega(n)$ time to find the minimum common element of two sets.
This doesn't mean that your application can't be solved efficiently. There still could be a way to solve your application in $O(n^2 \log n)$ time; this result doesn't rule that out.
In particular, when you have two sets, finding the minimum common element takes $\Omega(n)$ time. Indeed, testing disjointness requires $\Omega(n)$ time, as explained here. Now, imagine starting with two sets $S_1,S_2$ over the universe $\{1,2,\dots,n-1\}$. Let $T_1=S_1 \cup \{n\}$ and $T_2 = S_2 \cup \{n\}$. Now $T_1,T_2$ are guaranteed to have a common element. So, if you had a good data structure for your problem, store $T_1$ in one instance of the data structure and $T_2$ in another. Then, if we had a way to find the minimum element of $T_1 \cap T_2$ in $o(n)$ time, this would give us a way to test disjointness of $S_1,S_2$ in $o(n)$ time (just test whether the minimum element is smaller than $n$) -- but we already know the latter is not possible. It follows that the former is not possible, either, i.e., any data structure for your problem must take $\Omega(n)$ time to find the minimum common element of two sets.
This doesn't mean that your application can't be solved efficiently. There still could be a way to solve your application in $O(n^2 \log n)$ time; this result doesn't rule that out.
Context
StackExchange Computer Science Q#96222, answer score: 2
Revisions (0)
No revisions yet.