A Measure of Functions' Asymptotic Growth and the Complexity Classification of Computer Algorithms

In the development of algorithms and mathematics for software systems, the analysis is concerned with problem-solving algorithms and their software implementation. The impressive growth of contemporary computers' performance, apparently, should not weaken the requirements for algorithmic support, including the requirements for implementation efficiency. This is due to the fact that a number of actual computational tasks belong either to the NP-complete or to the NP-hard class, which have exact solution algorithms with a super-polynomial complexity. In this paper, a special angular measure of functions' asymptotic growth is offered, which allows one to distinguish between sub-polynomial, polynomial, sub-exponential, exponential and super-exponential functions. On the basis of the measure, an algorithm computational complexity classification is introduced oriented to application in theoretical and practical comparative analysis of computer algorithms.

Provided by: Journal of Computing Topic: Software Date Added: Nov 2012 Format: PDF

Find By Topic