Asymptotic computational complexity

Asymptotic computational complexity

                                                        Computer Science Fundamentals

noun phrase

Definition: The characterization of an algorithm’s resource usage, typically running time or memory usage, as a function of input size for sufficiently large inputs, usually expressed with asymptotic notation such as O, Θ, or Ω [Cormen et al. 2022].

Example in context: “The running time of merge sort is O(n lg ⁡n), in all cases, where $n$ is the number of elements being sorted.” [Cormen et al. 2022, 4th ed.]

Synonyms: asymptotic complexity

Related terms: time complexity; space complexity; Big-O notation; growth of functions