complexity function

complexity function (plural complexity functions )

1. (group theory , computing theory , of a string ) A function that counts the number of distinct factors (substrings of consecutive symbols) in a string of symbols;
   (of a formal language ) a function that counts the number of words of a given length.
   • 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 Theory, American Mathematical Society, page 27:

     It follows that
     ${\displaystyle \bullet }${\displaystyle \bullet } The length function ${\displaystyle l:A^{*}\longrightarrow {\mathcal {N}}}${\displaystyle l:A^{*}\longrightarrow {\mathcal {N}}} is a complexity function on ${\displaystyle A^{*}}${\displaystyle A^{*}}.

   • 2003, Julien Cassaigne, Constructing Infinite Words of Intermediate Complexity, Masami Ito, Masafumi Toyama (editors), Developments in Language Theory: 6th International Conference, 6th International Conference, DLT 2002, Revised Papers, Springer, LNCS 2450, page 173,

     We present two constructions of infinite words with a complexity function that grows faster than any polynomial, but slower than any exponential.

2. (computing theory , of an algorithm ) A function representing the computational complexity an algorithm.
   • 2003, Roberto Segala, Verification of Randomized Distributed Algorithms, Ed Brinksma, Holger Hermanns, Joost-Pieter Katoen (editors), Lectures on Formal Methods and Performance Analysis, Springer, LNCS 2090, page 253,

     Let ${\displaystyle \phi }${\displaystyle \phi } be a complexity function.

   • 2011, Richard Neapolitan, Kumarss Naimipour, Foundations of Algorithms, 4th edition, Jones & Bartlett Publishers, page 31:

     A complexity function need not have a quadratic term to be in ${\displaystyle O(n^{2})}${\displaystyle O(n^{2})}. It need only eventually lie beneath some pure quadratic function on a graph. Therefore, any logarithmic or linear complexity function is in ${\displaystyle O(n^{2})}${\displaystyle O(n^{2})}.

   • 2014, R. Panneerselvam, Research Methodology, 2nd edition, PHI Learning, page 512:

     Hence, the worst case time complexity function of Floyd's algorithm is ${\displaystyle O(n^{3})}${\displaystyle O(n^{3})}.

• abelian complexity function
• group complexity function
• time complexity function
• volume complexity function

• Computational complexity on Wikipedia.Wikipedia
• Formal language on Wikipedia.Wikipedia
• Sparse language on Wikipedia.Wikipedia

• English lemmas
• English nouns
• English countable nouns
• English multiword terms
• en:Group theory
• en:Theory of computing
• English terms with quotations

• Pages with entries
• Pages with 1 entry
• Entries with translation boxes
• Requests for translations into French
• Terms with German translations
• Requests for translations into Italian