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 |
|---|---|
| Clique problem | NP-complete via predicate surface "complexityClass" ⓘ |
| Subset sum problem | NP via predicate surface "complexityClass" ⓘ |
| Subset sum problem | exponential time for known exact algorithms in the worst case ⓘ |
|
Garey and Johnson: Computers and Intractability
surface form:
Computers and Intractability: A Guide to the Theory of NP-Completeness
|
Turing machine model via predicate surface "timeComplexityModel" ⓘ |
| Kemeny–Young method | NP-hard to compute exactly for many candidates via predicate surface "computationalComplexity" ⓘ |
| Miller primality test | polynomial in log n under GRH ⓘ |
| AKS primality test | polynomial in log n ⓘ |
| AKS primality test | O((log n)^{12}) via predicate surface "originalTimeComplexity" ⓘ |
| AKS primality test | O((log n)^{7.5}) via predicate surface "improvedTimeComplexity" ⓘ |
| alpha–beta pruning | O(b^(d/2)) via predicate surface "bestCaseComplexity" ⓘ |
| alpha–beta pruning | O(b^d) via predicate surface "worstCaseComplexity" ⓘ |
| Schoof–Elkies–Atkin (SEA) point-counting algorithm | polynomial in log(q) where q is the size of the finite field ⓘ |
| LLL algorithm | polynomial in the dimension and input size ⓘ |
| Rabin–Scott powerset construction | exponential in number of NFA states via predicate surface "worstCaseComplexity" ⓘ |
| sieve of Eratosthenes | O(n log log n) ⓘ |
| sieve of Eratosthenes | sub-quadratic in n via predicate surface "complexityClass" ⓘ |
| forward-backward algorithm | O(T·N²) ⓘ |
| forward-backward algorithm | linear in sequence length and quadratic in number of states via predicate surface "timeComplexityInWords" ⓘ |
| Bellman–Ford algorithm | O(V * E) via predicate surface "timeComplexityWorstCase" ⓘ |
| Bellman–Ford algorithm | O(V * E) via predicate surface "timeComplexityTypical" ⓘ |
| Tutte polynomial | #P-hard to evaluate at most points via predicate surface "computationalComplexity" ⓘ |
| Kosaraju's algorithm | O(V + E) ⓘ |
| Kosaraju's algorithm | linear-time algorithm via predicate surface "complexityClass" ⓘ |
| Kruskal’s minimum spanning tree algorithm | O(E log E) ⓘ |
| Kruskal’s minimum spanning tree algorithm | O(E log V) ⓘ |
| Dijkstra's shortest path algorithm | O(V^2) with adjacency matrix and simple array ⓘ |
| Dijkstra's shortest path algorithm | O((V + E) log V) with binary heap ⓘ |
| Dijkstra's shortest path algorithm | O(E + V log V) with Fibonacci heap ⓘ |
|
pairing heap (as a practical alternative)
surface form:
pairing heap
|
O(1) amortized via predicate surface "timeComplexityInsert" ⓘ |
|
pairing heap (as a practical alternative)
surface form:
pairing heap
|
O(1) amortized via predicate surface "timeComplexityMeld" ⓘ |
|
pairing heap (as a practical alternative)
surface form:
pairing heap
|
O(1) amortized via predicate surface "timeComplexityFindMin" ⓘ |
|
pairing heap (as a practical alternative)
surface form:
pairing heap
|
O(log n) amortized (under common analyses) via predicate surface "timeComplexityDeleteMin" ⓘ |
|
pairing heap (as a practical alternative)
surface form:
pairing heap
|
sub-logarithmic amortized in practice (theoretical bounds vary) via predicate surface "timeComplexityDecreaseKey" ⓘ |
| AVL tree | O(log n) via predicate surface "searchTimeComplexityAverage" ⓘ |
| AVL tree | O(log n) via predicate surface "searchTimeComplexityWorst" ⓘ |
| AVL tree | O(log n) via predicate surface "insertTimeComplexityAverage" ⓘ |
| AVL tree | O(log n) via predicate surface "insertTimeComplexityWorst" ⓘ |
| AVL tree | O(log n) via predicate surface "deleteTimeComplexityAverage" ⓘ |
| AVL tree | O(log n) via predicate surface "deleteTimeComplexityWorst" ⓘ |
| red-black tree | O(log n) via predicate surface "timeComplexitySearch" ⓘ |
| red-black tree | O(log n) via predicate surface "timeComplexityInsertion" ⓘ |
| red-black tree | O(log n) via predicate surface "timeComplexityDeletion" ⓘ |
| Prim's minimum spanning tree algorithm | O(V^2) via predicate surface "timeComplexityWithAdjacencyMatrix" ⓘ |
| Prim's minimum spanning tree algorithm | O(E log V) via predicate surface "timeComplexityWithBinaryHeap" ⓘ |
| Prim's minimum spanning tree algorithm | O(E + V log V) via predicate surface "timeComplexityWithFibonacciHeap" ⓘ |