complexity function

views updated

complexity function If A is an algorithm for solving a particular class of problems and n is a measure of the size of a particular problem in this class, then a complexity function fA(n) is a function of n giving an upper bound on the maximum number of basic operations that algorithm A has to perform to solve any problem of size n. For example, n might be the number of records in a file and fA(n) the maximum number of comparisons required to sort the file. There are many algorithms and problems where the number of basic operations depend on the data rather than the size of the data (e.g. Euclid's algorithm for greatest common divisors). See also complexity measure.

More From encyclopedia.com