- It gives rate of growth of step count function(f(n)) in terms of simple function(g(n)) and defines the asymptotic upper bound on function(Fig 1).
- To simplify the estimation for running time,constants and lower order terms are ignored.
- The function needs to satisfy following conditions in order to be in Big-O class.Given functions f(n) and g(n),we say f(n) is O(g(n)) if and if
- f(n) < c * g(n) for all n > n0
- where c and n0 are positive constants.
- The function n2 is does not belong to O(n) rather it belongs to O( n2 ) as it fails to satisfy the inequality f(n)<=cg(n).n2 cannot be less than n in any case as c is constant.
- O(..) is worst case (upper bound) notation for an algorithm’s complexity .
- Consider T(n)= 3n+2
- g(n) = n
- f(n) = 3n+2
- We need to find first value of c where answer comes positive.Let c=1
- f(n)<=c * g(n)
- 3n+2 <= c *n
- 3n+2 <= 1*n
- The answer comes in negative,so we cant choose c=1.
- Let c=2
- 3n+2 <= 2n The answer again comes in negative,so we cant choose c=2.
- 3n+2<=3n,can't choose c=3
- n0=2 and c=3.This is the point where f(n) and g(n) meets.
- Hence f(n)<=c*g(n) and thus belongs to big-O class.
- Highest power of n is 1.
- So f(n) belongs to O(n).
- Consider T(n) = 2n2 + 4
- f(n) = 2n2 + 4
- 2n2 + 4<=c *n2
- The inequality is false for c=1 and c=2.
2n2 + 4<=3 *n2
n=2 and n=-2,negative value is neglected.
- n>=2,n0=2 ,c=3
- Thus f(n) belongs to O(n2 ) .
- T(n) = 3n3+20n2+ 5
- 3n3+20n2+ 5 <=c * n3
- Is true for c=4 and n0 = 21
- Thus 3n3+20n2+ 5 belongs to O(n3).
- T(n) = 3 log n +5
- g(n) = log n
- f(n) = 3 log n +5
- f(n) <= c *g(n),c>0 and n > n0
- 3 log n + 5 <=c * log n
- c =8 and n0 = 2
- Thus 3n3+20n2+ 5 belongs to O(n3)
Complexities of algorithms
The various big 0 complexities are given in Fig 2 and Fig 3.