See complexity function in All languages combined, or Wiktionary
Download JSON data for complexity function meaning in English (6.1kB)
{
"forms": [
{
"form": "complexity functions",
"tags": [
"plural"
]
}
],
"head_templates": [
{
"args": {},
"expansion": "complexity function (plural complexity functions)",
"name": "en-noun"
}
],
"lang": "English",
"lang_code": "en",
"pos": "noun",
"senses": [
{
"categories": [
{
"kind": "topical",
"langcode": "en",
"name": "Group theory",
"orig": "en:Group theory",
"parents": [
"Algebra",
"Mathematics",
"Formal sciences",
"Sciences",
"All topics",
"Fundamental"
],
"source": "w"
},
{
"kind": "topical",
"langcode": "en",
"name": "Theory of computing",
"orig": "en:Theory of computing",
"parents": [
"Computer science",
"Computing",
"Sciences",
"Technology",
"All topics",
"Fundamental"
],
"source": "w"
},
{
"_dis": "45 45 9",
"kind": "other",
"name": "English entries with incorrect language header",
"parents": [
"Entries with incorrect language header",
"Entry maintenance"
],
"source": "w+disamb"
}
],
"examples": [
{
"ref": "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",
"text": "It follows that\nx5C;bullet The length function l#x3A;A#x2A;#x5C;longrightarrow#x5C;mathcalN is a complexity function on A#x2A;.",
"type": "quotation"
},
{
"text": "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,\nWe present two constructions of infinite words with a complexity function that grows faster than any polynomial, but slower than any exponential."
}
],
"glosses": [
"A function that counts the number of distinct factors (substrings of consecutive symbols) in a string of symbols;\n(of a formal language) a function that counts the number of words of a given length.",
"A function that counts the number of distinct factors (substrings of consecutive symbols) in a string of symbols;"
],
"id": "en-complexity_function-en-noun-WJEVi68K",
"links": [
[
"group theory",
"group theory"
],
[
"computing",
"computing#Noun"
],
[
"theory",
"theory"
],
[
"string",
"string"
],
[
"function",
"function"
],
[
"distinct",
"distinct"
],
[
"factor",
"factor"
],
[
"symbol",
"symbol"
],
[
"formal language",
"formal language"
]
],
"raw_glosses": [
"(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;\n"
],
"raw_tags": [
"of a string"
],
"topics": [
"computing",
"computing-theory",
"engineering",
"group-theory",
"mathematics",
"natural-sciences",
"physical-sciences",
"sciences"
]
},
{
"categories": [
{
"kind": "topical",
"langcode": "en",
"name": "Group theory",
"orig": "en:Group theory",
"parents": [
"Algebra",
"Mathematics",
"Formal sciences",
"Sciences",
"All topics",
"Fundamental"
],
"source": "w"
},
{
"kind": "topical",
"langcode": "en",
"name": "Theory of computing",
"orig": "en:Theory of computing",
"parents": [
"Computer science",
"Computing",
"Sciences",
"Technology",
"All topics",
"Fundamental"
],
"source": "w"
},
{
"_dis": "45 45 9",
"kind": "other",
"name": "English entries with incorrect language header",
"parents": [
"Entries with incorrect language header",
"Entry maintenance"
],
"source": "w+disamb"
}
],
"glosses": [
"A function that counts the number of distinct factors (substrings of consecutive symbols) in a string of symbols;\n(of a formal language) a function that counts the number of words of a given length.",
"a function that counts the number of words of a given length."
],
"id": "en-complexity_function-en-noun-KJAovTHs",
"links": [
[
"group theory",
"group theory"
],
[
"computing",
"computing#Noun"
],
[
"theory",
"theory"
],
[
"string",
"string"
],
[
"function",
"function"
],
[
"distinct",
"distinct"
],
[
"factor",
"factor"
],
[
"symbol",
"symbol"
],
[
"formal language",
"formal language"
]
],
"raw_glosses": [
"(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;\n"
],
"raw_tags": [
"of a formal language",
"of a string"
],
"topics": [
"computing",
"computing-theory",
"engineering",
"group-theory",
"mathematics",
"natural-sciences",
"physical-sciences",
"sciences"
]
},
{
"categories": [
{
"kind": "topical",
"langcode": "en",
"name": "Theory of computing",
"orig": "en:Theory of computing",
"parents": [
"Computer science",
"Computing",
"Sciences",
"Technology",
"All topics",
"Fundamental"
],
"source": "w"
}
],
"derived": [
{
"_dis1": "24 24 52",
"word": "abelian complexity function"
},
{
"_dis1": "24 24 52",
"word": "group complexity function"
},
{
"_dis1": "24 24 52",
"word": "time complexity function"
},
{
"_dis1": "24 24 52",
"word": "volume complexity function"
}
],
"examples": [
{
"text": "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,\nLet ϕ be a complexity function."
},
{
"text": "2011, Richard Neapolitan, Kumarss Naimipour, Foundations of Algorithms, 4th Edition, Jones & Bartlett Publishers, page 31,\nA complexity function need not have a quadratic term to be in O(n²). It need only eventually lie beneath some pure quadratic function on a graph. Therefore, any logarithmic or linear complexity function is in O(n²)."
},
{
"text": "2014, R. Panneerselvam, Research Methodology, 2nd Edition, PHI Learning, page 512,\nHence, the worst case time complexity function of Floyd's algorithm is O(n³)."
}
],
"glosses": [
"A function representing the computational complexity an algorithm."
],
"id": "en-complexity_function-en-noun-cr4qHmB3",
"links": [
[
"computing",
"computing#Noun"
],
[
"theory",
"theory"
],
[
"algorithm",
"algorithm"
],
[
"computational complexity",
"computational complexity"
]
],
"raw_glosses": [
"(computing theory, of an algorithm) A function representing the computational complexity an algorithm."
],
"raw_tags": [
"of an algorithm"
],
"topics": [
"computing",
"computing-theory",
"engineering",
"mathematics",
"natural-sciences",
"physical-sciences",
"sciences"
]
}
],
"wikipedia": [
"complexity function"
],
"word": "complexity function"
}
{
"categories": [
"English countable nouns",
"English entries with incorrect language header",
"English lemmas",
"English multiword terms",
"English nouns"
],
"derived": [
{
"word": "abelian complexity function"
},
{
"word": "group complexity function"
},
{
"word": "time complexity function"
},
{
"word": "volume complexity function"
}
],
"forms": [
{
"form": "complexity functions",
"tags": [
"plural"
]
}
],
"head_templates": [
{
"args": {},
"expansion": "complexity function (plural complexity functions)",
"name": "en-noun"
}
],
"lang": "English",
"lang_code": "en",
"pos": "noun",
"senses": [
{
"categories": [
"English terms with quotations",
"en:Group theory",
"en:Theory of computing"
],
"examples": [
{
"ref": "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",
"text": "It follows that\nx5C;bullet The length function l#x3A;A#x2A;#x5C;longrightarrow#x5C;mathcalN is a complexity function on A#x2A;.",
"type": "quotation"
},
{
"text": "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,\nWe present two constructions of infinite words with a complexity function that grows faster than any polynomial, but slower than any exponential."
}
],
"glosses": [
"A function that counts the number of distinct factors (substrings of consecutive symbols) in a string of symbols;\n(of a formal language) a function that counts the number of words of a given length.",
"A function that counts the number of distinct factors (substrings of consecutive symbols) in a string of symbols;"
],
"links": [
[
"group theory",
"group theory"
],
[
"computing",
"computing#Noun"
],
[
"theory",
"theory"
],
[
"string",
"string"
],
[
"function",
"function"
],
[
"distinct",
"distinct"
],
[
"factor",
"factor"
],
[
"symbol",
"symbol"
],
[
"formal language",
"formal language"
]
],
"raw_glosses": [
"(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;\n"
],
"raw_tags": [
"of a string"
],
"topics": [
"computing",
"computing-theory",
"engineering",
"group-theory",
"mathematics",
"natural-sciences",
"physical-sciences",
"sciences"
]
},
{
"categories": [
"English terms with quotations",
"en:Group theory",
"en:Theory of computing"
],
"glosses": [
"A function that counts the number of distinct factors (substrings of consecutive symbols) in a string of symbols;\n(of a formal language) a function that counts the number of words of a given length.",
"a function that counts the number of words of a given length."
],
"links": [
[
"group theory",
"group theory"
],
[
"computing",
"computing#Noun"
],
[
"theory",
"theory"
],
[
"string",
"string"
],
[
"function",
"function"
],
[
"distinct",
"distinct"
],
[
"factor",
"factor"
],
[
"symbol",
"symbol"
],
[
"formal language",
"formal language"
]
],
"raw_glosses": [
"(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;\n"
],
"raw_tags": [
"of a formal language",
"of a string"
],
"topics": [
"computing",
"computing-theory",
"engineering",
"group-theory",
"mathematics",
"natural-sciences",
"physical-sciences",
"sciences"
]
},
{
"categories": [
"en:Theory of computing"
],
"examples": [
{
"text": "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,\nLet ϕ be a complexity function."
},
{
"text": "2011, Richard Neapolitan, Kumarss Naimipour, Foundations of Algorithms, 4th Edition, Jones & Bartlett Publishers, page 31,\nA complexity function need not have a quadratic term to be in O(n²). It need only eventually lie beneath some pure quadratic function on a graph. Therefore, any logarithmic or linear complexity function is in O(n²)."
},
{
"text": "2014, R. Panneerselvam, Research Methodology, 2nd Edition, PHI Learning, page 512,\nHence, the worst case time complexity function of Floyd's algorithm is O(n³)."
}
],
"glosses": [
"A function representing the computational complexity an algorithm."
],
"links": [
[
"computing",
"computing#Noun"
],
[
"theory",
"theory"
],
[
"algorithm",
"algorithm"
],
[
"computational complexity",
"computational complexity"
]
],
"raw_glosses": [
"(computing theory, of an algorithm) A function representing the computational complexity an algorithm."
],
"raw_tags": [
"of an algorithm"
],
"topics": [
"computing",
"computing-theory",
"engineering",
"mathematics",
"natural-sciences",
"physical-sciences",
"sciences"
]
}
],
"wikipedia": [
"complexity function"
],
"word": "complexity function"
}
This page is a part of the kaikki.org machine-readable English dictionary. This dictionary is based on structured data extracted on 2024-05-05 from the enwiktionary dump dated 2024-05-02 using wiktextract (f4fd8c9 and c9440ce). The data shown on this site has been post-processed and various details (e.g., extra categories) removed, some information disambiguated, and additional data merged from other sources. See the raw data download page for the unprocessed wiktextract data.
If you use this data in academic research, please cite Tatu Ylonen: Wiktextract: Wiktionary as Machine-Readable Structured Data, Proceedings of the 13th Conference on Language Resources and Evaluation (LREC), pp. 1317-1325, Marseille, 20-25 June 2022. Linking to the relevant page(s) under https://kaikki.org would also be greatly appreciated.