**In this post we are discussing about What are the various basic efficiency classes? Explain Big O Big Omega and Big Theta asymptotic notations**

**Basic asymptotic Efficiency Classes**:-

Class | Name | Comments |

1 | constant | Short of best-case efficiencies, very few reasonable examples can be given since an algorithm •s running time typically goes to infinity when its input Size grows infinitely large. |

log n | logarithmic | Typically. a result of cutting a problem’s size by a constant factor on each iteration of the algorithm . Note that a logarithmic algorithm cannot take into account all its input or even a fixed fraction Of it: any algorithm that does so will have at least linear running time. |

n | linear | Algorithms that scan a list of size n (e.g., sequential search) belong to this class. |

n * log n | linearithmic | Many divide-and-conquer algorithms , including mergesort and quicksort in the average case, fall into this category. |

n^{2} | quadratic | Typically, characterizes efficiency of algorithms with two embedded loops (see the next section). Elementary sorting algorithms and certain operations on n x n matrices are standard examples. |

n^{3} | cubic | typically, characterizes efficiency of algorithms with three embedded loops (see the next section). Several nontrivial algorithms from linear algebra fall into this class |

2^{n} | exponential | Typical for algorithms that generate all subsets of an n-element set. Often. the term “exponential” is used in a broader sense to include this and larger orders Of growth as well. |

n! | factorial | Typical for algorithms that generate all permutations of an n-element set. |

1.**Big-Oh notation:-**

**Definition: **A function *t(n) *is said to be in *O(g(n)), *denoted *t(n)*∈*O(g(n)), *if t (n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some nonnegative integer n_{0} such that

*t(n) ≤ c g(n) for all n ≥ n*_{0}.

Informally, *O(g(n)) *is the set of all functions with a lower or same order of growth as *g(n)*

**2. Big-Omega notation**:-

**Definition: **A function t(n) is said to be in Ω(g(n)), denoted ** t(n)**∈

**if t(n) is bounded below by some positive constant multiple of g(n) for all large n, i.e., positive constant c and some nonnegative integer n**

*Ω(g(n)),*_{0}such that

*t(n) ≥ c g(n) for all n ≥ n _{0}.*

**3. Big-Theta notation:-**

A function t(n) is said to be in **Θ(g(n)), **denoted **t(n) **∈ **Θ(g(n)), **if t (n) is bounded both above and below by some positive constant multiples of g(n) for all large n, i.e., if there exist some positive constants c_{1} and c_{2} and some nonnegative integer n_{0} such that

**c _{2} g(n) ≤ t(n) ≤ c_{1}g(n) for all n ≥ n_{0}.**