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.