4
$\begingroup$

This problem involves the time-complexity of determining set intersections, and the algorithm must give output on all possible inputs (as described below).

Problem 1: The input is a positive integer $m$, and two unordered subsets $A$ and $B$ of $\{1,\dots,n\}$. The size of the input is $n+ |A| +|B|$.

Output: The set $A \cap B$, the intersection of $A$ and $B$.

As all infinitely many possibilities are ranged through, with the size of output $n = m + |A| + |B|$, is there a linear-time algorithm that on any $(n,A,B)$, outputs $A \cap B$? Is there an $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients? (Worst-case complexity.)

Problem 2: The input is a positive integer $m$, and $j$ unordered subsets $A_1, \dots, A_j$ of $\{1,\dots,n\}$. The size of the input is $n+ |A_1| + \cdots + |A_n|$.

Output: $A_1 \cap A_2 \cap \cdots \cap A_n$, the intersection of $A_1, \dots, A_j$.

As all infinitely many possibilities are ranged through, with the size of output $n = m + |A| + |B|$, is there a linear-time algorithm that on any $(n,A,B)$, outputs $A \cap B$? Is there an $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients? (Worst-case complexity.)

Are there references to the time complexity of these problems? I’m interested in the particular algorithms themselves, but if anyone knows that complexities above are linear-time or $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients, I’d be grateful to hear from you. ( I’m less interested in algorithms that involve hash functions, but as long as such an algorithm works on all possible inputs, a hash function algorithm is okay.) I’m not a computer scientist student but an older person learning things as they come along in work-in-progress.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ This sounds like homework. Please tell us what you tried. For problem 1, could you clarify what is $m$? Assuming $m$ is extraneous, you can tell we need to at least read the entire input (worst case)? It seems you can check existence of each $i \in \{1, \ldots, n\}$ in constant time - what does that tell you about the overall complexity? Problem 2 builds on problem 1 in a straightforward way $\endgroup$ – Reinstate Monica Aug 6 '18 at 1:45
  • 1
    $\begingroup$ You seem to have mixed up $n$ and $m$. You also seem to have copied some text from Problem 1 to Problem2. Finally, note that you actually have two questions. The usual rule is one question per post. $\endgroup$ – Yuval Filmus Aug 6 '18 at 1:49
2
$\begingroup$

Your post contains two problems. I will only address the first.

There is a simple $O(n)$ algorithm for computing $A \cap B$, which involves an array of length $n$.

Another algorithm sorts $A \cup B$ to find the intersection in time $O(n\log n)$. In contrast to the previous algorithm, this algorithm can be implemented using only comparisons. There is a matching $\Omega(n\log n)$ lower bound in the algebraic decision tree model; see for example lecture notes of Otfried Cheong.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I'm not a student, nor have been for 30+ years.... Thank you for the answer to the first question... I take it that O(n) algorithm would involve hash sets, or some more advance methods than comparisons? Thanks again--Steven (I'll post my second question as a single question.) $\endgroup$ – Steven48 Aug 6 '18 at 2:14
  • $\begingroup$ There is absolutely no need for any hash. The elements are already in the range $1,\ldots,n$, and can function as their own hash. $\endgroup$ – Yuval Filmus Aug 6 '18 at 2:15
  • $\begingroup$ What then would O(n) look like? I get the O(n log n) one [put sets into one array, order, find elements that repeat], but have no idea at all how to do O(n). [Mathematician, old 70, working on something involving time complexity...learning.] $\endgroup$ – Steven48 Aug 6 '18 at 2:17
  • 1
    $\begingroup$ The only way to learn is to solve exercises. There's no point in my spelling out the answer. $\endgroup$ – Yuval Filmus Aug 6 '18 at 2:18
0
$\begingroup$

You can’t give the time complexity because a set is not a primitive data structure, so you need to know how it is represented.

Why would n be part of the input size? Let A = { 1,000,000,000 } and B = { 1, 1,000,000,000 }, for example.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ We want to measure resource consumption in terms of $n$ rather than in terms of the input length. This allows us to compute the intersection of $A$ and $B$ in linear although the actual running time is $\Theta(n)$. $\endgroup$ – Yuval Filmus Aug 6 '18 at 13:13

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.