complexity function

More Like This

Show all results sharing this subject:

  • Computing


Show Summary Details

Quick Reference

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.

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.