Big-O notation
E679192
Big-O notation is a mathematical tool used in computer science to describe how the running time or space requirements of an algorithm grow relative to the size of its input.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
asymptotic notation
ⓘ
complexity analysis tool ⓘ mathematical notation ⓘ |
| alsoKnownAs | O-notation NERFINISHED ⓘ |
| appliedIn |
algorithm design
ⓘ
computational complexity theory ⓘ data structure analysis ⓘ performance engineering ⓘ |
| assumes | sufficiently large input size ⓘ |
| basedOn | asymptotic analysis ⓘ |
| characterizes |
upper bound on growth rate of a function
ⓘ
worst-case complexity of an algorithm ⓘ |
| commonExample |
O(1)
ⓘ
O(2^n) ⓘ O(log n) ⓘ O(n log n) ⓘ O(n!) ⓘ O(n) ⓘ O(n^2) ⓘ |
| compares |
growth of memory usage to input size
ⓘ
growth of running time to input size ⓘ |
| contrastsWith |
average-case analysis when used for worst-case bounds
ⓘ
exact running time measurement ⓘ |
| describes |
asymptotic upper bound ignoring constant factors
ⓘ
asymptotic upper bound ignoring lower-order terms ⓘ |
| field |
computer science
ⓘ
mathematics ⓘ |
| formalDefinitionInvolves |
existence of positive constants c and n0
ⓘ
inequality |f(n)| ≤ c·g(n) for all n ≥ n0 ⓘ |
| helpsWith |
choosing algorithms for large-scale problems
ⓘ
predicting algorithm performance for large inputs ⓘ |
| ignores |
constant-time differences
ⓘ
machine-dependent constants ⓘ |
| originatedIn | mathematical analysis ⓘ |
| relatedTo |
Big-Omega notation
NERFINISHED
ⓘ
Big-Theta notation ⓘ Landau notation NERFINISHED ⓘ little-o notation ⓘ little-omega notation ⓘ |
| symbol | O ⓘ |
| taughtIn |
data structures courses
ⓘ
introductory algorithms courses ⓘ theoretical computer science courses ⓘ |
| usedFor |
analyzing scalability of algorithms
ⓘ
comparing algorithm efficiency ⓘ describing algorithm space complexity ⓘ describing algorithm time complexity ⓘ describing growth rates of functions ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.