Average running time analysis of an algorithm to calculate the size of the union of Cartesian products Original Research Article

We consider the problem of calculating the size of the union of Cartesian products of finite sets of integers Sij, |⋃i=1,…,n Si1×⋯×Sim|, where m denotes the dimension of the space and n the number of Cartesian products. This problem, denoted by SUCP, contains as a special case the problem of counting the number of satisfying assignments of the satisfiability problem (SAT). We present an algorithm to solve the problem SUCP, called the grouping method. For the average running time analysis, Sij are constructed by randomly selecting each element in set D={1,2,…,d} with probability p. We show that the average running time of the grouping method is O(mnd·min{(nd(1−p)+1)m−1,dm−1}), which is more efficient than the time complexity O(mndm) of the naive method if n(1−p)⪡1 holds.