A New Asymptotic Notation: Weak Theta

Andrei-Horia Mogoş, Bianca Mogoş and Adina Magda Florea

Mathematical Problems in Engineering, 2015, vol. 2015, 1-15

Abstract:

Algorithms represent one of the fundamental issues in computer science, while asymptotic notations are widely accepted as the main tool for estimating the complexity of algorithms. Over the years a certain number of asymptotic notations have been proposed. Each of these notations is based on the comparison of various complexity functions with a given complexity function. In this paper, we define a new asymptotic notation, called “Weak Theta,” that uses the comparison of various complexity functions with two given complexity functions. Weak Theta notation is especially useful in characterizing complexity functions whose behaviour is hard to be approximated using a single complexity function. In addition, in order to highlight the main particularities of Weak Theta, we propose and prove several theoretical results: properties of Weak Theta, criteria for comparing two complexity functions, and properties of a new set of complexity functions (also defined in the paper) based on Weak Theta. Furthermore, to illustrate the usefulness of our notation, we discuss an application of Weak Theta in artificial intelligence.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2015/912962.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2015/912962.xml (text/xml)

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:hin:jnlmpe:912962

DOI: 10.1155/2015/912962

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().