Big O notation

Big O notation describes an asymptotic upper bound on a function’s growth. In algorithm analysis, it characterizes how time or space requirements scale with input size, ignoring constant factors and lower-order terms.

Asymptotic analysis: The study of functions’ growth rates as their inputs become large. Big O is one of the main notations used to express asymptotic growth.
Algorithm analysis: The study of an algorithm’s resource use and performance as a function of input size. Big O is a standard language for expressing algorithm-analysis results.
Linear search: A search algorithm that checks sequence elements one by one until finding a target or reaching the end. Its worst-case running time grows linearly with the number of elements.
Big Omega notation: A notation expressing an asymptotic lower bound on a function’s growth. It gives the lower-bound counterpart to Big O’s upper bound.
Big O definition: A formal condition stating that one function is eventually bounded above by a constant multiple of another. This definition specifies exactly what an O-bound guarantees.
Input size: A measure of the amount of data an algorithm receives, often represented by n. Complexity functions express resource use in terms of input size.
Binary search: A search algorithm that repeatedly halves a sorted search interval. Its logarithmic running time contrasts sharply with linear search.
Asymptotic equivalence: A relation in which the ratio of two functions approaches one as the input grows. It is more precise than Big O when two functions have the same leading behavior.
Worst-case complexity: The maximum resource use an algorithm can require for inputs of a given size. Worst-case analyses commonly report an upper bound using Big O.
Growth rate: The rate at which a quantity changes as its input or independent variable increases. Big O compares functions by their growth as input size increases.

Linked from 29 pages