# Sort complexity expressed via distinct number of elements

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.

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.

• 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? – user1242967 Feb 9 '17 at 21:30
• 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. – Yuval Filmus Feb 9 '17 at 21:37
• 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. – user1242967 Feb 9 '17 at 21:52

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$.

• How do you eliminate duplicates in $O(a)$? – Yuval Filmus Feb 9 '17 at 21:18
• 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. – user3543290 Feb 9 '17 at 21:22
• 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. – Yuval Filmus Feb 9 '17 at 21:25
• I think it is assumed in the article that hashing is not used to eliminate duplicates in A. – user1242967 Feb 9 '17 at 21:32