This notation describes asymptotic behavior of functions.

O(x)

A function f is O(g(x)) if, for large x, g(x) is as large or larger than f(x) up to scaling.

Θ(x)

A function f is Θ(g(x)) if, for large x, f(x) is as large as g(x) up to scaling.

Ω(x)

A function f is O(g(x)) if, for large x, f(x) is as large or larger than g(x) up to scaling.

Examples

Any f(x) is O(f(x)), Θ(f(x)), and Ω(f(x)).

2x is O(x), O(5x), O(x²), but not O(log(x)).

2x is Θ(x), Θ(5x), but not Θ(x²) or Θ(log(x)).

2x is Ω(x), Ω(5x), not Ω(x²), but Ω(log(x)).

[todo: motivation for these constructs]