complexity functions

Noun

complexity function (plural complexity functions)

1. A function that counts the number of distinct factors (substrings of consecutive symbols) in a string of symbols;
   • It follows that
     #92;bullet The length function l#58;A#42;#92;longrightarrow#92;mathcalN is a complexity function on A#42;.2002, A. V. Borovnik, A. G. Myasnikov, V. Shpilrain, “Measuring Sets in Infinite Groups”, in Robert H. Gilman, Alexei G. Myasnikov, Vladimir Shpilrain, editors, Computational and Statistical Group...
2. a function that counts the number of words of a given length.
3. A function representing the computational complexity an algorithm.
   • Let ϕ be a complexity function.2003, Roberto Segala, Verification of Randomized Distributed Algorithms, Ed Brinksma, Holger Hermanns, Joost-Pieter Katoen (editors), Lectures on Formal Methods and Performance Analysis, Springer...