Comparing Two Multivariable Complexity Functions Using One-variable Complexity Classes

Abstract

The comparison of algorithms complexities is very important both in theory and in practice. When we compare algorithms complexities we need to compare complexity functions. Usually we use one-variable complexity functions. Sometimes, we need multivariable complexity func-tions. In a previous paper we defined several one-variable complexity classes for multivariable complexity functions. Each complexity class of this type is a set of multivariable complexity functions, represented by a one-variable complexity function. In this paper we continue the work from that paper: we define new one-variable complexity classes and we prove several properties. The most important results are several criteria for two multivariable complexity functions to be comparable.

Keywords

• Algorithm
• One-Variable Complexity Class
• One-Variable Complexity Function
• Multivariable Complexity Function
• Functions Comparison