Asymptotic Notation | big O omega theta

Asymptotic Notation

Asymptotic Notation Growth of Functions:

Measuring the performance of an algorithm in relation with input size n is called Order of growth. The order of growth for varying for varying input size of n is as given below.

Asymptotic Notation

Asymptotic Notation

Asymptotic Notation :

Asymptotic notation enables us to make meaningful statements about the time and space complexities of an algorithm due to their inexactness. It is used to express running time of an algorithm as a function of input size n for large n and expressed using only the highest-order term in the expression for the exact running time

3 notations widely used are for measuring time complexity:

  1. Big ‘oh’ notation (O)
  2. Big omega notation (Ω)
  3. Theta notation (θ)

Big oh notation:

The f(n) = O(g(n)) ( f(n) is O of g(n)) iff for some constants c and n0.
f(n) <= c*g(n) for all n, n>=n0 where f and g are non-negative functions
g(n) is an upper-bound on the value of f(n)
In f(n) = O(g(n)), ‘=’ is to be read as ‘is’ but not as ‘equals’, as f(n) = O(g(n)) is not equal  to O(g(n)) = f(n)

Asymptotic Notation

Example:
f(n) T(P)
3n+2

10n2 +4n+2

6*2n + n2

O(n)

O(n2)

O(2n)

3n+2 <= 4n for all n>=2

10n2 +4n+2 <= 11n2 for all n>=5

6*2n + n2 <= 7*2n for all n>=4

Omega notation:

The f(n) = Ω (g(n)) ( f(n) is Ω of g(n)) iff for some constants c and n0.
f(n) >= c*g(n) for all n, n>=n0 where f and g are non-negative functions
g(n) is an lower-bound on the value of f(n)

Asymptotic Notation

 

Example:
f(n) T(P)
3n+2

10n2 +4n+2

6*2n + n2

Ω(n)

Ω(n2)

Ω(2n)

3n+2 >= 3n for all n>=2

10n2 +4n+2 >= 10n2 for all n>=5

6*2n + n2 >= 6*2n for all n>=4

Theta notation:

The f(n) = θ (g(n)) ( f(n) is θ of g(n)) iff for some constants c1,c2 and n0

c1*g(n)<= f(n) <= c*g(n) ¥ n, n>=n0 where f and g are non-negative functions g(n) is both an upper-bound and a lower-bound on the value of f(n)

It is denoted by θ.

Example:
f(n) T(P)
3n+2

10n2 +4n+2

6*2n + n2

θ (n)

θ (n2)

θ (2n)

3n <= 3n+2 <= 4n for all n>=2

10n2 <= 10n2 +4n+2 <= 11n2 for all n>=5

6*2n <= 6*2n + n2 <= 7*2n for all n>=4

Little oh notation

It is defined as: Let, f(n) and g(n) be the non-negative functions then lim 𝑛→∞ 𝑓(𝑛)/𝑔(𝑛) = 0 such that f(n)=o(g(n)). f(n)=o(g(n)) if and only if f(n)=o(g(n)) and f(n)≠θ (g(n)). It is denoted as o.

Little omega notation 

It is defined as: Let, f(n) and g(n) be the non-negative functions then lim𝑛→∞ 𝑔(𝑛)/𝑓(𝑛) = 0 such that f(n)=Ω(g(n)). It is denoted as Ω.

 

Topic : Asymptotic Notation | big O omega theta

Leave a Reply