Abstract
In [2], a new problem called conditional cartesian product problem was introduced. The problem has a trivial time lower bound Ω(⌈|C A.B |/N⌉), where A and B are two groups of N elements and C A,B is a subset of the cartesian product A × B satisfying some unknown condition C. Ben-Asher proposed an efficient algorithm for the problem and showed that the proposed algorithm can be performed in O(loglogN × ⌈|C A,B |/N⌉ compared with the trivial time lower bound, the algorithm is not optimal. In this paper, with a better analysis, we show that the worst-case time complexity of Ben-Asher's algorithm is O(loglogN + |C A,B |/N), which is much better than O(loglogN × ⌈|C A,B |/N⌉). Consequently, it can be concluded that for case the rate of growth of |C A,B | is not smaller than O(NloglogN),Ω(⌈|C A,B |/N⌉) is a tight lower bound and Ben-Asher's algorithm is indeed optimal. © World Scientific Publishing Company.