Definition of Complexity measure

FOLDOC
complexity measure
<algorithm> A quantity describing the complexity of a computation.
(1996-04-24)

Search Dictionary:
Search Web Search Dictionary



Complexity measure definition was found in categories: Encyclopedia(1)  

Complexity measure Definition from Encyclopedia Dictionaries & Glossaries

Wikipedia English - The Free Encyclopedia
Blum axioms
In computational complexity theory the Blum axioms or Blum complexity axioms are axioms  which specify desirable properties of complexity measures on the set of computable functions. The axioms were first defined by Manuel Blum in 1967.

Importantly, the Speedup and Gap theorems hold for any complexity measure satisfying these axioms. The most well-known measures satisfying these axioms are those of time (i.e., running time) and space (i.e., memory usage).


See more at Wikipedia.org...