timeComplexity
P27167
predicate
Indicates the computational growth rate of an algorithm’s resource usage (typically time) as a function of input size.
All labels observed (54)
| Label | Occurrences |
|---|---|
| timeComplexity canonical | 34 |
| complexityClass | 21 |
| computationalComplexity | 9 |
| timeComplexityAmortized | 7 |
| timeComplexityWorstCase | 7 |
| hasTimeComplexity | 6 |
| timeComplexityBestCase | 4 |
| timeComplexityAverageCase | 3 |
| worstCaseComplexity | 3 |
| complexityMeasure | 2 |
| timeComplexityDeletion | 2 |
| timeComplexityFocus | 2 |
| timeComplexityInsertion | 2 |
| timeComplexitySearch | 2 |
| worstCaseTimeComplexity | 2 |
| algorithmComplexity | 1 |
| averageCaseTimeComplexity | 1 |
| backwardTraversalComplexity | 1 |
| bestCaseComplexity | 1 |
| bestCaseTimeComplexity | 1 |
| complexityQuantum | 1 |
| deleteTimeComplexityAverage | 1 |
| deleteTimeComplexityWorst | 1 |
| forwardTraversalComplexity | 1 |
| improvedTimeComplexity | 1 |
| insertTimeComplexityAverage | 1 |
| insertTimeComplexityWorst | 1 |
| numberOfComparisonsWorstCase | 1 |
| originalTimeComplexity | 1 |
| preprocessingPhaseComplexity | 1 |
| searchPhaseComplexity | 1 |
| searchTimeComplexityAverage | 1 |
| searchTimeComplexityWorst | 1 |
| timeComplexityConstraint | 1 |
| timeComplexityDecreaseKey | 1 |
| timeComplexityDeleteMin | 1 |
| timeComplexityDescription | 1 |
| timeComplexityFindMin | 1 |
| timeComplexityForm | 1 |
| timeComplexityHeapify | 1 |
| timeComplexityInWords | 1 |
| timeComplexityInsert | 1 |
| timeComplexityMeld | 1 |
| timeComplexityModel | 1 |
| timeComplexityNlargest | 1 |
| timeComplexityNsmallest | 1 |
| timeComplexityPop | 1 |
| timeComplexityPush | 1 |
| timeComplexityType | 1 |
| timeComplexityTypical | 1 |
| timeComplexityWithAdjacencyMatrix | 1 |
| timeComplexityWithBinaryHeap | 1 |
| timeComplexityWithFibonacciHeap | 1 |
| typicalDFTComplexity | 1 |
Description generation (PDg)
The one-sentence description above was generated by prompting gpt-5.1 with the predicate name and this instruction.
Instruction
Given a predicate that represents a relationship or action between entities, generate a one-sentence description explaining its meaning. # Instructions Focus on describing the relationship, not the entities themselves. # Response Format Begin the description with \' Indicates...\'
Input
Predicate: timeComplexity
Generated description
Indicates the computational growth rate of an algorithm’s resource usage (typically time) as a function of input size.
Sample triples (145)
| Subject | Object |
|---|---|
| Boyer–Moore string-search algorithm | O(n + m) average time via predicate surface "hasTimeComplexity" ⓘ |
| Boyer–Moore string-search algorithm | O(nm) worst-case time via predicate surface "hasTimeComplexity" ⓘ |
| Deutsch–Jozsa algorithm | O(n) via predicate surface "complexityQuantum" ⓘ |
| Cooley–Tukey Fast Fourier Transform algorithm | O(N log N) via predicate surface "hasTimeComplexity" ⓘ |
| Cooley–Tukey Fast Fourier Transform algorithm | O(N^2) via predicate surface "typicalDFTComplexity" ⓘ |
| Schmidt orthogonalization | O(n^2 m) for n vectors in R^m (classical implementation) ⓘ |
| Lloyd’s algorithm | O(n k d i) ⓘ |
| Lloyd’s algorithm | n data points, k clusters, d dimensions, i iterations via predicate surface "timeComplexityDescription" ⓘ |
| BidirectionalCollection | O(1) per step via predicate surface "forwardTraversalComplexity" ⓘ |
| BidirectionalCollection | O(1) per step via predicate surface "backwardTraversalComplexity" ⓘ |
| SymTridiagonal | O(n)Storage ⓘ |
| SymTridiagonal | O(n)MatrixVectorMultiply ⓘ |
| heapq | O(log n) via predicate surface "timeComplexityPush" ⓘ |
| heapq | O(log n) via predicate surface "timeComplexityPop" ⓘ |
| heapq | O(n) via predicate surface "timeComplexityHeapify" ⓘ |
| heapq | O(n log k) via predicate surface "timeComplexityNlargest" ⓘ |
| heapq | O(n log k) via predicate surface "timeComplexityNsmallest" ⓘ |
| Rabin–Karp algorithm | O(n + m) via predicate surface "timeComplexityAverageCase" ⓘ |
| Rabin–Karp algorithm | O(nm) via predicate surface "timeComplexityWorstCase" ⓘ |
|
Hamiltonian cycle concept
surface form:
Hamiltonian cycle problem
|
NP-complete via predicate surface "complexityClass" ⓘ |
| Lomuto partition scheme | O(n) for partition step ⓘ |
| Merge sort | O(n log n) via predicate surface "timeComplexityBestCase" ⓘ |
| Heapsort | O(n log n) via predicate surface "timeComplexityWorstCase" ⓘ |
| Heapsort | O(n log n) via predicate surface "numberOfComparisonsWorstCase" ⓘ |
| Insertion sort | O(n^2) via predicate surface "timeComplexityWorstCase" ⓘ |
| Insertion sort | O(n) via predicate surface "timeComplexityBestCase" ⓘ |
| Hoare partition scheme | O(n) via predicate surface "timeComplexityAverageCase" ⓘ |
| Hamming distance | O(n) in string length via predicate surface "computationalComplexity" ⓘ |
| Napier's bones | reduces multiplication to addition and reading off partial products via predicate surface "computationalComplexity" ⓘ |
| SAT problem | NP via predicate surface "complexityClass" ⓘ |
|
Karp reductions
surface form:
Karp reduction
|
polynomial time via predicate surface "timeComplexityConstraint" ⓘ |
| Fermat primality test | polynomial in log n ⓘ |
| Steiner tree problem | NP-complete in graphs via predicate surface "complexityClass" ⓘ |
| Steiner tree problem | NP-hard in Euclidean plane via predicate surface "complexityClass" ⓘ |
| Max-3-SAT | NP-hard via predicate surface "complexityClass" ⓘ |
| Narendra Karmarkar | polynomial time via predicate surface "algorithmComplexity" ⓘ |
| Gale–Shapley algorithm | O(n^2) ⓘ |
| Dedekind number | exact computation is extremely difficult for large n via predicate surface "computationalComplexity" ⓘ |
| Tomohiko Sakamoto’s algorithm | O(1) ⓘ |
| Cantor–Zassenhaus algorithm | expected polynomial time in degree and log(q) via predicate surface "complexityClass" ⓘ |
| Aho–Corasick algorithm | O(n + m + z) via predicate surface "hasTimeComplexity" ⓘ |
| Aho–Corasick algorithm | linear in length of text plus total length of patterns plus number of matches via predicate surface "hasTimeComplexity" ⓘ |
| Post correspondence problem | RE-complete via predicate surface "complexityClass" ⓘ |
|
complexity class EXPTIME
surface form:
EXPTIME
|
O(2^{p(n)}) for some polynomial p via predicate surface "timeComplexityForm" ⓘ |
|
complexity class BPP
surface form:
BPP
|
randomized time complexity via predicate surface "complexityMeasure" ⓘ |
|
complexity class RP
surface form:
RP
|
time complexity measured in worst-case polynomial time via predicate surface "complexityMeasure" ⓘ |
| SAT | NP via predicate surface "complexityClass" ⓘ |
| SAT | NP-complete via predicate surface "complexityClass" ⓘ |
| SAT | believed not solvable in polynomial time unless P = NP via predicate surface "worstCaseComplexity" ⓘ |
| 3-SAT | NP via predicate surface "complexityClass" NERFINISHED ⓘ |