Properties of Asymptotic Notations

Software Development
1

General Properties:

  • If a function f(n) is O(g(n)), then there exists a scalar constant a such that a * f(n) is also equals to O(g(n))
    e.g., Suppose, f(n) = 2 * n + 5 which is O(n), then7 * f(n) = 14 * n + 35 = O(n)

  • Reflexive: If f(n) is given, then f(n) is O(f(n))
    e.g., Suppose, f(n) = n + 3, then f(n) = O(n)

  • Transitive: If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n))
    e.g., Let f(n) = n, g(n) = n^2, and h(n) = n^3,
    From reflexive Property: f(n) = O(n), g(n) = O(n^2), and h(n) = O(n^3)
    then, f(n) = O(n^3) is True.

Please refer Asymptotic Notations - Big Oh - Software Development - Discussion Forum | Board Infinity to find why the above equation is True.

3

Extra properties for complexity lovers who want to learn more about Asymptotic Notations:

  • Symmetric: If a function f(n) is Θ(g(n)), then the function g(n) is Θ(f(n))
    e.g., Suppose f(n) = n^2 = n * n and g(n) = n^2 = n * n,
    then the function f(n) = Θ(nn) which is Θ(g(n)) in this case, then g(n) = Θ(nn) which is Θ(f(n))

  • Transpose: if f(n) = O(g(n)), then g(n) = Ω(f(n))
    e.g., Suppose a function f(n) = n = O(n^2), then the function g(n) = n^2 = Ω(n) which is equal to Ω(f(n)).

Q.E.D.

4

Thanks.

Thank You so much for sharing this.