Complexity notations

记录一下计算复杂度理论中的一些记号。
-notation (also called Big notation), -notation (Omega notation), and -notation (Theta notation) are mathematical notations used in computer science and computational complexity theory to describe the behavior of functions and algorithms.

-notation

-notation represents the upper bound or worst-case behavior of a function or algorithm.
It provides an asymptotic upper bound on the growth rate of a function.
In simpler terms, it describes the maximum amount of resources (time or space) that an algorithm requires as a function of the input size, without being excessively pessimistic.
Formally, is used to denote that a function, say , is asymptotically bounded above by .
Mathematically, this means that there exists a positive constant such that for all sufficiently large values of , .

-notation

Ω-notation represents the lower bound or best-case behavior of a function or algorithm.
It indicates the minimum amount of resources required.
Formally, is used to denote that a function, say , is bounded below by asymptotically.
Mathematically, this means that there exists a positive constant such that for all sufficiently large values of , .

For example, if an algorithm has a time complexity of , it means that the running time of the algorithm is at least linear with the input size.

-notation

-notation represents the tight bound or average-case behavior of a function or algorithm.
It provides both the upper and lower bounds on the growth rate of a function, indicating that the function grows at the same rate as the bound.
Formally, is used to denote that a function, say , is asymptotically bounded both above and below by .
Mathematically, this means that there exist positive constants and such that for all sufficiently large values of , .

For example, if an algorithm has a time complexity of Θ(n^2), it means that the running time of the algorithm grows quadratically with the input size, and the upper and lower bounds match.