Comparing Two Multivariable Complexity Functions Using One-variable Complexity Classes

Andrei Horia Mogos () and Adina Magda Florea ()

Informatica Economica, 2009, vol. 13, issue 4, 116-128

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 (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://revistaie.ase.ro/content/52/12%20-%20Mogos,%20Florea.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:aes:infoec:v:13:y:2009:i:4:p:116-128

Access Statistics for this article

Informatica Economica is currently edited by Ion Ivan

More articles in Informatica Economica from Academy of Economic Studies - Bucharest, Romania Contact information at EDIRC.
Bibliographic data for series maintained by Paul Pocatilu ().