A New Asymptotic Notation: Weak Theta
Open Access
- 4 October 2015
- journal article
- research article
- Published by Hindawi Limited in Mathematical Problems in Engineering
- 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.Keywords
Funding Information
- Ministry of European Funds (POSDRU/159/1.5/S/132397)
This publication has 10 references indexed in Scilit:
- Swarm Intelligence and Its Applications 2014The Scientific World Journal, 2014
- Binary Structuring Elements Decomposition Based on an Improved Recursive Dilation‐Union Model and RSAPSO MethodMathematical Problems in Engineering, 2014
- Artificial Intelligence and Its ApplicationsMathematical Problems in Engineering, 2014
- Multiagent Reinforcement Learning with Regret Matching for Robot SoccerMathematical Problems in Engineering, 2013
- Isotonic Regression for Multiple Independent VariablesAlgorithmica, 2013
- Finite-time consensus algorithm for multi-agent systems with double-integrator dynamicsAutomatica, 2011
- A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithmJournal of Global Optimization, 2007
- Improved master theorems for divide-and-conquer recurrencesJournal of the ACM, 2001
- On the Solution of Linear Recurrence EquationsComputational Optimization and Applications, 1998
- Crusade for a better notationACM SIGACT News, 1985