A fast algorithm for the disjunctive decomposition of m-valued functions. II. Time complexity analysis

摘要

For part I see ibid., p.118-25. The time complexity of the fast algorithm for the disjunctive decomposition of m-valued functions, proposed in part I is studied. A probabilistic approach is used to estimate the time complexity for random m-valued functions, where several statistical properties of such functions are obtained and used in the analysis. It is shown that the time complexity for random functions is of the order of (nm)/sup 3/. In the case in which a random function has a single disjunctive decomposition, the time complexity becomes of the order n/sup 3/m/sup n/. The algorithm was simulated on a digital computer. The experimental results are in agreement with the theoretical predictions.