Hardy notation

From Wikipedia, the free encyclopedia

In complexity theory and mathematics, the Hardy notation, introduced by G. H. Hardy, is used for asymptotic comparison of functions, equivalently to Landau notation (also known as "Big O notation").

It is defined in terms of Landau notation by

f\lesssim g \iff f \in O(g)   and   f\ll g \iff f\in o(g).


(Similar symbols are used, like \preceq resp. \prec\!\!\!\!\!\!\!\!\prec.)

The Hardy notation is commonly abused similarly to the Landau notation. For example, where h2 = O(h3) is the shortened/abused Landau notation of h\mapsto h^2 \in O(h\mapsto h^3), the expression h^2 \lesssim h^3 is the shortened/abused Hardy notation of h\mapsto h^2 \lesssim h\mapsto h^3.

For more examples and applications, see Landau notation and references therein.

[edit] See also

Languages