complexity function

From Wiktionary, the free dictionary
Jump to navigation Jump to search

English

[edit]
English Wikipedia has an article on:
Wikipedia

Noun

[edit]

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
      The length function is a complexity function on .
    • 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 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 . It need only eventually lie beneath some pure quadratic function on a graph. Therefore, any logarithmic or linear complexity function is in .
    • 2014, R. Panneerselvam, Research Methodology, 2nd Edition, PHI Learning, page 512,
      Hence, the worst case time complexity function of Floyd's algorithm is .

Derived terms

[edit]

Translations

[edit]

Further reading

[edit]