A Generalized Set Theoretic Approach for Time and Space Complexity Analysis of Algorithms and Functions

摘要

There exists a variety of techniques for analyzing the computational complexity of algorithms and functions. This analysis is critical in finding out the upper and the lower bounds on time and space requirements using the big-oh and the big-omega notations. Besides these, there are other complexity criteria, such as, small omega and small o complexities, which are also useful. Complexity analysis is used in selecting an appropriate algorithm for solving a given problem using computer. Unfortunately, most of the existing techniques are complex, obsolete and hard to use in practice. Besides, there is a trend to abuse notational complexities by considering them as functions. However, notational complexities are sets of functions rather than bare functions. In this paper, it has been established that the notational complexities are sets of functions that include all algorithms and functions on the given order satisfying certain constraints. Moreover, starting from the scratch, we show how to determine the time and space complexity functions for a given computational algorithm. We consider application of the proposed framework in determining the notational complexities. The proposed framework may be extended for functions involving multiple variables. Also the space-time bandwidth product has been discussed in deciding the economy of using the computational algorithms.