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. |
| n2 | 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. |
| n3 | cubic | typically, characterizes efficiency of algorithms with three embedded loops (see the next section). Several nontrivial algorithms from linear algebra fall into this class |
| 2n | 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 n0 such that
t(n) ≤ c g(n) for all n ≥ n0.
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)∈ Ω(g(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 n0 such that
t(n) ≥ c g(n) for all n ≥ n0.
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 c1 and c2 and some nonnegative integer n0 such that
c2 g(n) ≤ t(n) ≤ c1g(n) for all n ≥ n0.
