Hashing LEMMAs on time complexities with applications to formula manipulation

Abstract

In this paper, time complexities of operation on “sets” and “ordered n-tuples” based on a hashing table search technique are presented as “Hashing LEMMAs” and are applied to formula manipulation. Unique normal forms for multivariate symbolic formulas resulting in O(1) time complexity for identity checks are presented. The logarithmic factor log2N, characteristic to sorting algorithms, is shown to all disappear from time complexities of polynomial manipulations. Actual implementation of the hashing technique is outlined and actual timing data are presented in the appendix.