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 |
|---|---|
| Gaussian elimination | O(n^3) for an n by n system ⓘ |
| Conway polynomial | can be computed in polynomial time for fixed crossing number but is generally hard for large diagrams via predicate surface "computationalComplexity" ⓘ |
|
Ising model
linked to:
Ising models
|
NP-hard for general graphs via predicate surface "computationalComplexity" ⓘ |
| Euler’s totient function φ(n) | φ(n) can be computed efficiently if the prime factorization of n is known via predicate surface "computationalComplexity" ⓘ |
| shunting-yard algorithm | O(n) ⓘ |
| B-tree | O(log n) via predicate surface "timeComplexitySearch" ⓘ |
| B-tree | O(log n) via predicate surface "timeComplexityInsertion" ⓘ |
| B-tree | O(log n) via predicate surface "timeComplexityDeletion" ⓘ |
| Knuth–Morris–Pratt algorithm | O(n + m) ⓘ |
| Knuth–Morris–Pratt algorithm | O(n) via predicate surface "timeComplexityBestCase" ⓘ |
| Knuth–Morris–Pratt algorithm | O(n + m) via predicate surface "timeComplexityWorstCase" ⓘ |
| Knuth–Morris–Pratt algorithm | O(m) via predicate surface "preprocessingPhaseComplexity" ⓘ |
| Knuth–Morris–Pratt algorithm | O(n) via predicate surface "searchPhaseComplexity" ⓘ |
| Quicksort | O(n log n) via predicate surface "timeComplexityBestCase" ⓘ |
| Quicksort | O(n log n) via predicate surface "timeComplexityAverageCase" ⓘ |
| Quicksort | O(n^2) via predicate surface "timeComplexityWorstCase" ⓘ |
| Thompson's algorithm for regular expression matching | O(n·m) for matching, where n is input length and m is NFA size ⓘ |
| Thompson's algorithm | O(n) in size of regular expression via predicate surface "complexityClass" ⓘ |
| Regular Expression Search Algorithm | varies by implementation ⓘ |
| Regular Expression Search Algorithm | linear time for DFA-based implementations ⓘ |
| Regular Expression Search Algorithm | potentially exponential time for naive backtracking implementations ⓘ |
| Berlekamp’s algorithm for factoring polynomials over finite fields | polynomial time in the degree and log of field size via predicate surface "complexityClass" ⓘ |
| Berlekamp–Massey algorithm | O(n^2) via predicate surface "hasTimeComplexity" ⓘ |
| Borda count | winner determination is polynomial time via predicate surface "computationalComplexity" ⓘ |
| Adleman–Pomerance–Rumely primality test | polynomial time under GRH via predicate surface "timeComplexityType" ⓘ |
| Davis–Putnam algorithm | worst-case exponential time via predicate surface "complexityClass" ⓘ |
| Viterbi algorithm | O(N^2 T) ⓘ |
| Viterbi algorithm | O(S^2 T) ⓘ |
| Dehn function | linear for hyperbolic groups via predicate surface "complexityClass" ⓘ |
| Dehn function | quadratic for many automatic groups via predicate surface "complexityClass" ⓘ |
| Dehn function | at least quadratic for non-hyperbolic nilpotent groups of step ≥ 2 via predicate surface "complexityClass" ⓘ |
| The Complexity of Theorem-Proving Procedures | polynomial time via predicate surface "timeComplexityFocus" ⓘ |
| The Complexity of Theorem-Proving Procedures | nondeterministic polynomial time via predicate surface "timeComplexityFocus" ⓘ |
| union–find data structure | amortized inverse Ackermann time per operation with union by rank and path compression ⓘ |
| union–find data structure | near-constant time per operation in practice ⓘ |
| union–find data structure | O(α(n)) per operation with union by rank and path compression via predicate surface "worstCaseTimeComplexity" ⓘ |
| Fibonacci heap | O(1) for insert via predicate surface "timeComplexityAmortized" ⓘ |
| Fibonacci heap | O(1) for find-minimum via predicate surface "timeComplexityAmortized" ⓘ |
| Fibonacci heap | O(1) for decrease-key via predicate surface "timeComplexityAmortized" ⓘ |
| Fibonacci heap | O(1) for merge via predicate surface "timeComplexityAmortized" ⓘ |
| Fibonacci heap | O(log n) for delete-minimum via predicate surface "timeComplexityAmortized" ⓘ |
| Fibonacci heap | O(log n) for delete via predicate surface "timeComplexityAmortized" ⓘ |
| Fibonacci heap | O(n) for build-heap by repeated insert via predicate surface "worstCaseTimeComplexity" ⓘ |
| splay tree | O(log n) via predicate surface "timeComplexityAmortized" ⓘ |
| splay tree | O(n) via predicate surface "timeComplexityWorstCase" ⓘ |
| Tarjan's strongly connected components algorithm | O(V + E) ⓘ |
| Tarjan's strongly connected components algorithm | linear in the size of the graph via predicate surface "complexityClass" ⓘ |
| Fibonacci search | O(log n) ⓘ |
| Fibonacci search | O(1) via predicate surface "bestCaseTimeComplexity" ⓘ |
| Fibonacci search | O(log n) via predicate surface "averageCaseTimeComplexity" ⓘ |