Facebook

Big O Notation

 

  • 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 nis 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 .
Fig 1: Big O Notation
Fig 1: Big O Notation

 

Example 1

  • 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.
  • c=3
  • 3n+2<=3n,can't choose c=3
  • c=4
  • 3n+2<=4n
  • n>=2
  • 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).

Example 2

  • Consider  T(n) = 2n2 + 4
  • g(n)=n
  • f(n) = 2n2 + 4
  •  2n2 + 4<=c *n
  • The inequality is false for c=1 and c=2.
  • c=3

2n2 + 4<=3 *n

4<=n

n=2 and n=-2,negative value is neglected.

  • n>=2,n0=2 ,c=3
  • Thus f(n) belongs to O(n) .

Example 3

  • T(n) = 3n3+20n2+ 5
  • 3n3+20n2+ 5 <=c * n
  • Is true for c=4 and n= 21
  • Thus 3n3+20n2+ 5 belongs to O(n3).

Example 4

  • 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 n= 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.

Screen Shot 2014-07-25 at 6.27.09 PM
Fig 2: Complexities of sorting algorithms
Screen Shot 2014-09-11 at 12.56.46 PM
Fig 3 : Complexities of sorting algorithms

 

 

 

1 (20%) 1 vote

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar