# 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

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. Fig 2: Complexities of sorting algorithms Fig 3 : Complexities of sorting algorithms

3.3 (65%) 4 votes

## Comments

So empty here ... leave a comment!
Sidebar