timeComplexity
P27167
predicate
Indicates the computational growth rate of an algorithm’s resource usage (typically time) as a function of input size.
Aliases (8)
- computationalComplexity ×3
- preprocessingPhaseComplexity ×1
- searchPhaseComplexity ×1
- timeComplexityBestCase ×1
- timeComplexityDeletion ×1
- timeComplexityInsertion ×1
- timeComplexitySearch ×1
- timeComplexityWorstCase ×1
Sample triples (13)
| Subject | Object |
|---|---|
| B-tree | O(log n) ("timeComplexitySearch") → |
| B-tree | O(log n) ("timeComplexityInsertion") → |
| B-tree | O(log n) ("timeComplexityDeletion") → |
| Conway polynomial | can be computed in polynomial time for fixed crossing number but is generally hard for large diagrams ("computationalComplexity") → |
| Euler’s totient function φ(n) | φ(n) can be computed efficiently if the prime factorization of n is known ("computationalComplexity") → |
| Gaussian elimination | O(n^3) for an n by n system → |
| Ising model | NP-hard for general graphs ("computationalComplexity") → |
| Knuth–Morris–Pratt algorithm | O(m) ("preprocessingPhaseComplexity") → |
| Knuth–Morris–Pratt algorithm | O(n + m) → |
| Knuth–Morris–Pratt algorithm | O(n + m) ("timeComplexityWorstCase") → |
| Knuth–Morris–Pratt algorithm | O(n) ("timeComplexityBestCase") → |
| Knuth–Morris–Pratt algorithm | O(n) ("searchPhaseComplexity") → |
| shunting-yard algorithm | O(n) → |