asymptotic notation

What Is Asymptotic Notation ?

Tech Tips

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}

Big-O Notation
Big-O Notation

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}

Omega-Notation
Omega-Notation

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}

Theta-Notation
Theta-Notation

Download The Full Pdf Version Of This Note

Click Here To Download

For Networking Note Click Here

Leave a Reply

Your email address will not be published. Required fields are marked *