See complexity function on Wiktionary
{
"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"
}
],
"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\n#92;bullet The length function l#58;A#42;#92;longrightarrow#92;mathcalN is a complexity function on A#42;.",
"type": "quote"
},
{
"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;"
],
"id": "en-complexity_function-en-noun-d5JKkOun",
"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;"
],
"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": "27 51 22",
"kind": "other",
"name": "English entries with incorrect language header",
"parents": [
"Entries with incorrect language header",
"Entry maintenance"
],
"source": "w+disamb"
},
{
"_dis": "25 53 21",
"kind": "other",
"name": "Entries with translation boxes",
"parents": [],
"source": "w+disamb"
},
{
"_dis": "30 47 23",
"kind": "other",
"name": "Pages with 1 entry",
"parents": [],
"source": "w+disamb"
},
{
"_dis": "26 54 21",
"kind": "other",
"name": "Pages with entries",
"parents": [],
"source": "w+disamb"
},
{
"_dis": "20 64 16",
"kind": "other",
"name": "Terms with German translations",
"parents": [],
"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;"
],
"raw_tags": [
"of a formal language",
"of a string"
],
"topics": [
"computing",
"computing-theory",
"engineering",
"group-theory",
"mathematics",
"natural-sciences",
"physical-sciences",
"sciences"
],
"translations": [
{
"_dis1": "28 67 5",
"code": "de",
"lang": "German",
"sense": "function that counts distinct words of a given length in a language",
"tags": [
"feminine"
],
"word": "Komplexitätsfunktion"
}
]
},
{
"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": "22 24 54",
"word": "abelian complexity function"
},
{
"_dis1": "22 24 54",
"word": "group complexity function"
},
{
"_dis1": "22 24 54",
"word": "time complexity function"
},
{
"_dis1": "22 24 54",
"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"
],
"translations": [
{
"_dis1": "21 23 56",
"code": "de",
"lang": "German",
"sense": "function that represents the computational complexity of an algorithm",
"tags": [
"feminine"
],
"word": "Komplexitätsfunktion"
}
]
}
],
"translations": [
{
"_dis1": "47 46 6",
"code": "de",
"lang": "German",
"sense": "function that counts distinct factors of a string",
"tags": [
"feminine"
],
"word": "Komplexitätsfunktion"
}
],
"wikipedia": [
"complexity function"
],
"word": "complexity function"
}
{
"categories": [
"English countable nouns",
"English entries with incorrect language header",
"English lemmas",
"English multiword terms",
"English nouns",
"Entries with translation boxes",
"Pages with 1 entry",
"Pages with entries",
"Terms with German translations"
],
"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\n#92;bullet The length function l#58;A#42;#92;longrightarrow#92;mathcalN is a complexity function on A#42;.",
"type": "quote"
},
{
"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;"
],
"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;"
],
"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;"
],
"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"
]
}
],
"translations": [
{
"code": "de",
"lang": "German",
"sense": "function that counts distinct factors of a string",
"tags": [
"feminine"
],
"word": "Komplexitätsfunktion"
},
{
"code": "de",
"lang": "German",
"sense": "function that counts distinct words of a given length in a language",
"tags": [
"feminine"
],
"word": "Komplexitätsfunktion"
},
{
"code": "de",
"lang": "German",
"sense": "function that represents the computational complexity of an algorithm",
"tags": [
"feminine"
],
"word": "Komplexitätsfunktion"
}
],
"wikipedia": [
"complexity function"
],
"word": "complexity function"
}
Download raw JSONL data for complexity function meaning in All languages combined (5.2kB)
This page is a part of the kaikki.org machine-readable All languages combined dictionary. This dictionary is based on structured data extracted on 2025-01-25 from the enwiktionary dump dated 2025-01-20 using wiktextract (c15a5ce and 5c11237). 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.