2
$\begingroup$

I am reading Probabilistic counting algorithms for database applications. In the introduction an algorithm for finding an intersection is specified:

Sort A, search each element of B in A and retain it if it appears in A.

It is claimed that if a, b are number of elements in A and B, and $\alpha, \beta$ are the number of distinct elements in A, B then the complexity of this algorithm is $O(a\log\alpha + b\log\alpha)$. My question is, why the sorting of A is only dependent on the number of distinct elements? Is there some kind of algorithm I am not aware of? If so, why the same algorithm could not be used for the second strategy? The second strategy is:

Sort A and B, use merge-like operation to discard duplicates.

For this algorithm the complexity is $O(a\log a + b\log b + a + b)$ which makes sense to me.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

You can use a balanced binary search tree to sort $A$ in time $O(a\log\alpha)$ by going over the elements of $A$, for each element searching whether it already appears in the tree, inserting it if it isn't already there. You can then perform the second stage in $O(\log \alpha)$ per element of $B$, for a total of $O(b\log\alpha)$.

If you are allowed to use hashing on the elements of $A$ and $B$, then you can use a dynamic hash table to compute the intersection in expected $O(a+b)$ time by using a similar strategy.

Improve this answer
$\endgroup$
3
  • $\begingroup$ And how do you check if the element is already in the tree? You still have to travel down the tree like with any other element or not? $\endgroup$
    – user1242967
    Feb 9, 2017 at 21:30
  • $\begingroup$ Searching for an element in a (balanced) tree of size $n$ takes time $O(\log n)$. Here the tree contains every element exactly once, so $n \leq \alpha$, which makes it $O(\log \alpha)$ per element. $\endgroup$
    – Yuval Filmus
    Feb 9, 2017 at 21:37
  • $\begingroup$ Ok, I guess it makes sense but I don't really understand why wouldn't the same logic be applied to the strategy 2. As I understand the article tries to convince that choosing the better strategy depends on the amount of distinct elements in A and B but it is not clear from the example. But I am not sure if cs.stackexchange is the right place for explaining scientific articles. $\endgroup$
    – user1242967
    Feb 9, 2017 at 21:52
0
$\begingroup$

Observe that we can eliminate duplicate elements in $A$ in time linear in $a$. So, the process of eliminating elements and then sorting is $O(a + \alpha \log \alpha)$ which I claim is $O(a \log \alpha)$ for $a > \alpha$.

The runtime you give for your algorithm is indeed $O(a \log a + b \log b)$ since the linear terms you give are taken by the poly log terms. To see this, observe that $2 a \log a > a \log a + a$ for all sufficiently large $a$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How do you eliminate duplicates in $O(a)$? $\endgroup$
    – Yuval Filmus
    Feb 9, 2017 at 21:18
  • $\begingroup$ Go through the list, hash each element to a bucket. If the bucket is already full, do nothing. At the end, you just empty your buckets. $\endgroup$
    – user3543290
    Feb 9, 2017 at 21:22
  • $\begingroup$ If you are allowed to use hashing, then you can improve the performance to $O(a+b)$. It seems that at this stage, the book is interested in comparison-based algorithms. $\endgroup$
    – Yuval Filmus
    Feb 9, 2017 at 21:25
  • $\begingroup$ I think it is assumed in the article that hashing is not used to eliminate duplicates in A. $\endgroup$
    – user1242967
    Feb 9, 2017 at 21:32

Your Answer

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

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