A New Paradigm for the Computational Complexity Analysis of Algorithms and Functions

Abstract — There exists a variety of techniques for the computa-tional complexity analysis of algorithms and functions. This analysis is foundational to the algorithmic and the functional performance. Asides from the big-oh complexity, there are other complexity notations, such as Ω, Θ, small o and small ω notational complexities. Complexity analysis is used to select an appropriate algorithm for solving a given problem using computer. Unfortunately, most of the prevailing approaches lack in simplicity, and consistency. Existing techniques are complex, and rather hard to realize in practice. There is a trend to exploit the notational complexities in the existing literature by treating those as functions instead of sets. In this paper, notational complexities and their applications paradigms are studied from the new perspectives. Simplified and consistent approaches are introduced that will make the analysis even simpler and easy to understand. Abused notational complexities are analyzed through the appropriate approach. Also, the paradigm introduced is extended to algorithms and functions involving multiple input variables