PROPERTIES OF ASYMPTOTIC NOTATIONS

Properties of Asymptotic Notations

Till now we have seen all asymptotic notations(ASN), Now we shall see the properties of these asymptotic notations. But before these properties we'll see some analogy between ASN and Real No.
Analogy Between ASN and  Real Numbers:
Let f and g be the functions and a and b be the real numbers.
1. f(x) is O(g(x)) ⇔ a ≤ b
2. f(x) is Ω(g(x)) ⇔ a ≥ b
3. f(x) is Θ(g(x)) ⇔ a = b
4. f(x) is o(g(x)) ⇔ a < b
5. f(x) is ω(g(x)) ⇔ a > b

Properties of ASN:
1. Discrete:

Properties like symmetric, reflexive, transitive

2. Trichotomy:
This property says " For any two real numbers a and b exactly one of the following must hold
a<b, a=b or a>b
But sometime this is true for ASN not always. Let me explain by taking some examples.
example 1:  log n  and n
                    log n = O(n) or n = Ω(log n)
example 2: n and n^(1+sin x)
                    here we can not say anything because sin x value varies from -1 to 1.
                    if sin x = -1 then n^(1-1)⇒1
                    ⇒ n > 1
                    ⇒ n^(1+sin x) = O(n)
BUT            if sin x = 1 then n^(1+1)⇒n²
                    ⇒ n < n²
                    ⇒ n= O(n^(1+sin x))

General properties:
Let f,g,d,e be the functions
1. if f(x) is O(g(x)) then [a.f(x)] is O(g(x)) , where a is a constant , a>0
2. if f(x) is O(g(x)) and d(x) is O(e(x)) then
    i) f(x)+d(x) is O(max(g(x),e(x)))
        example: n + n² = O(max(n,n²)) = O(n²)
   ii) f(x)*d(x) is O(g(x)*e(x))
        example: n*n² = O(n³)