# 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 > n**_{0}- where
**c**and**n**are_{0 }**positive**constants.

- The function
**n**is does not belong to^{2 }**O(n)**rather it belongs to**O( n**as it fails to satisfy the inequality^{2 })**f(n)<=cg(n)**.**n**^{2 }cannot be less than**n**in any case as**c**is constant. -
**O(..)**is**worst case**(upper bound**) notation**for an algorithm’s**complexity**.

**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****n**and_{0}=2**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) =
**2n**^{2}+ 4 **g(n)=n**^{2 }- f(n) =
**2n**^{2}+ 4 - 2n
^{2}+ 4<=c *n^{2 } - The inequality is false for c=1 and c=2.
- c=3

2n^{2} + 4<=3 *n^{2 }

4<=n^{2 }

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

**n>=2,n**_{0}=2 ,c=3- Thus
**f(n) belongs to O(n**.^{2 })

**Example 3**

- T(n) =
**3n**^{3}+20n^{2}+ 5 - 3n
^{3}+20n^{2}+ 5 <=c * n^{3 } - Is true for
**c=4**and**n**_{0 }= 21 - Thus
**3n**belongs to^{3}+20n^{2}+ 5**O(n**.^{3})

**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 >****n**_{0} - 3 log n + 5 <=c * log n
**c =8**and**n**_{0 }= 2- Thus
**3n**belongs to^{3}+20n^{2}+ 5**O(n**^{3})

### Complexities of algorithms

The various big 0 complexities are given in Fig 2 and Fig 3.

* *

## Comments

So empty here ... leave a comment!