What is Asymptotic Notation ?
Asymptotic Notation :-
Asymptotic notation is used to describe the running time of an algorithm. This shows the order of growth of function. Asymptotic notation describe the algorithm efficiency and performed in a meaningful way. Asymptotic notation also describe the behavior of time or space complexity for large instance characteristics.
Commonly three notation are use :
1. Big-O notation.
2. Big-Omega notation.
3. Big-Theta notation.
Big-O notation :-
It deals with the maximum time required by the algorithm f(n) is said to be O(g(n)) if there exists a positive constants c and no. Such that h(n)<=c.g(n) for all n>=no.
Big-O notation gives the upper bound of time requires by the algorithm.
Big-Omega notation :-
It deals with the minimum time (best case) required by an algorithm ,f(n) is said to be Omega (g(n)) if there exists positive constant and no such that if (n)>=c * g(n) for all n>=n0,c>0.
Omega gives the lower bound of time required by the algorithm.
Big-Theta notation :-
It deals with the average time required by the algorithm f(n) is Theta(g(n)) if there exits positive constants c1,c2 and n0 such that -
C1 g(n)<=f(n)<=c2 g(n) for all n>=n0
Theta notation denote the asymptotic right bounce of time complexity required by the algorithm.
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment