## 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 *f*_{A}(*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 *f*_{A}(*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.

## Related content in Oxford Index

##### Reference entries

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