Asymptotic Notation:
Formal way to speak about function and classify them we will to describe time of algorithm.
1) O (Big-o)
2) Theta
3) Big-omega
1) O (Big -0) (upper Bound):-This is a Worst Case.It is the set of all function a smaller or the same order of growth as f(n).
Little-oh notation :little-oh of g of n as the set
o(g(n))={f(n): for any positive constant c>0 , n0>0 such that 0=<f(n)<cg(n)
or
o(g(n)) is the set of all function with a smaller rate of growth than f(n).
Big Omega:-This is a Average Case.
Let f and g are non-negative function,The function f(n)=Omega(g(n)) if there exit positive constant c and n0.
Big Theta:- This is a Best Case.
Let f and g are non-negative function.The function f(n)=theta(g(n))
if there exit positive constant C1,C2 and n0 such that c1 g(n)<=f(n)<=C2g(n) for all n, n>=n0.
1) O (Big-o)
2) Theta
3) Big-omega
1) O (Big -0) (upper Bound):-This is a Worst Case.It is the set of all function a smaller or the same order of growth as f(n).
O(n2)={2n2,2n+1
, logn…….}
2n2=o(n2)
2n=o(n2)
Little-oh notation :little-oh of g of n as the set
o(g(n))={f(n): for any positive constant c>0 , n0>0 such that 0=<f(n)<cg(n)
or
o(g(n)) is the set of all function with a smaller rate of growth than f(n).
Big Omega:-This is a Average Case.
Let f and g are non-negative function,The function f(n)=Omega(g(n)) if there exit positive constant c and n0.
Big Theta:- This is a Best Case.
Let f and g are non-negative function.The function f(n)=theta(g(n))
if there exit positive constant C1,C2 and n0 such that c1 g(n)<=f(n)<=C2g(n) for all n, n>=n0.
No comments