# What Is Asymptotic Notation ?

### Asymptotic Notation .

Asymptotic Notation Are the expression that are used to represent the complexity of an algorithm.

Using Asymptotic notation we can very well concluded that what are the Best Case ,Average Case and Worst Case.

Best Case – Performance of an algorithm for input takes less time or space

Average Case – Performance of an algorithm for input takes average time or space

Worst Case – Performance of an algorithm for input takes long time or space

### Types Of Notations

There are three types of notations

1. Big O Notations ( O )
2. Omega Notations( Ω )
3. Theta Notations( θ )

#### 1. Big O Notations

It represent the Upper Bound running time complexity of an algorithm

It measures the Worst Case time complexity

f(n) = O(g(n)) if All +ve Constant c and n0 such that O<= f(n) <= cg(n) all n>=0

Here f(n) = Small and g(n)=bigger

Example

O(f(n)) ={ g(n) = there exist c > 0 and n0 such that f(n) <= c.g(n) for all n>n0}

#### 2. Omega Notation ( Ω )

It represent the Upper Bound running time complexity of an algorithm

It measures the Best Case time complexity.

f(n) = Ω (g(n)) if All +ve constant c and n0 such that O<= cg(n) <=f(n) all n>=0

Here f(n) = Bigger and g(n)=Small

Example

O(f(n)) ={ g(n) = there exist c > 0 and n0 such that f(n) <= c.g(n) for all n>n0}

#### 3. Theta Notation ( θ )

It represent the both Upper Bound as well as lower bound running time complexity of an algorithm.

It measures the Worst Case time complexity.

f(n) = O(g(n)) if All +ve Constant c1 , c2 and n0 such that c1(g(n))<= f(n) <= c2(g(n)) for all n>=0

Here c1(g(n)) = small f(n) = middle and c2(g(n))=bigger

Example

θ (f(n)) ={ g(n) if and only if g(n) = o(f(n)) and g(n) = Ω (f(n)) for all n>n0}