SKEDSOFT

Design Analysis Of Algorithm

Comparison of functions: Many of the relational properties of real numbers apply to asymptotic comparisons as well. For the following, assume that f(n) and g(n) are asymptotically positive.

Transitivity:

Reflexivity:

f(n)

=

Θ(f(n)),

f(n)

=

O(f(n)),

f(n)

=

Ω(f(n)).

Symmetry:

f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n)).

Transpose symmetry:

f(n) = O(g(n))

if and only if

g(n) = Ω(f(n)),

f(n) = o(g(n))

if and only if

g(n) = ω(f(n)).

Because these properties hold for asymptotic notations, one can draw an analogy between the asymptotic comparison of two functions f and g and the comparison of two real numbers a and b:

f(n) = O(g(n))

ab,

f(n) = Ω(g(n))

ab,

f(n) = Θ(g(n))

a= b,

f(n) = o(g(n))

a< b,

f(n) = ω(g(n))

a> b.

We say that f(n) is asymptotically smaller than g(n) if f(n) = o(g(n)), and f(n) is asymptotically larger than g(n) if f(n) = ω(g(n)).

One property of real numbers, however, does not carry over to asymptotic notation:

Trichotomy:For any two real numbers a and b, exactly one of the following must hold: a < b, a = b, or a > b.

Although any two real numbers can be compared, not all functions are asymptotically comparable. That is, for two functions f(n) and g(n), it may be the case that neither f(n) = O(g(n)) nor f(n) = Ω(g(n)) holds. For example, the functions n and n1 sin n cannot be compared using asymptotic notation, since the value of the exponent in n1 sin n oscillates between 0 and 2, taking on all values in between.