Routledge Dictionary of Language and Linguistics
complexity (also computational complexity)
Analysis of algorithms in terms of the time and memory resources they demand. Because algorithms apply to classes of input problems, their complexity is expressed as a function of input size: for example, one can search an ordered list (e.g. a dictionary) in time proportional to a (base 2) logarithm of list size. Because the time and memory used by concrete algorithms vary by a constant factor for irrelevant reasons (e.g. owing to the machine or compiler used), complexity is expressed in abstraction from constant factors.
Thus, searching an ordered list of length n is O(log n), i.e. of the order logarithmic. (
also tractable)
References
Barton, G., R.Berwick, and E.Ristad. 1987. Computational complexity and natural language. Cambridge.
Garey, M. and D.Johnson, 1979. Computers and intractability: a guide to the theory of NP completeness. New York.
This is the complete article, containing 139 words
(approx. 1 page at 300 words per page).
View More Summaries on Complexity
