## Asymptotic Notation

**Asymptotic Notation Growth of Functions:**

Measuring the performance of an algorithm in relation with input size n is called Order of growth. The order of growth for varying for varying input size of n is as given below.

**Asymptotic Notation :**

Asymptotic notation enables us to make meaningful statements about the time and space complexities of an algorithm due to their inexactness. It is used to express running time of an algorithm as a function of input size n for large n and expressed using only the highest-order term in the expression for the exact running time

3 notations widely used are for measuring time complexity:

- Big ‘oh’ notation (O)
- Big omega notation (Ω)
- Theta notation (θ)

**Big oh notation:**

The **f(n) = O(g(n)) ( f(n) is O of g(n))** iff for some constants *c *and *n*_{0}.

**f(n) <= c*g(n)** for all** n, n>=n _{0}** where f and g are non-negative functions

g(n) is an upper-bound on the value of f(n)

In

**f(n) = O(g(n))**, ‘=’ is to be read as ‘is’ but not as ‘equals’,

**as f(n) = O(g(n)) is not equal**

**to O(g(n)) = f(n)**

Example: |
|||

f(n) | T(P) | ||

3n+2
10n2 +4n+2 6*2n + n2 |
O(n)
O(n2) O(2n) |
3n+2 <= 4n for all n>=2
10n2 +4n+2 <= 11n2 for all n>=5 6*2n + n2 <= 7*2n for all n>=4 |

**Omega notation:**

The **f(n) = Ω (g(n)) ( f(n) is Ω of g(n))** iff for some constants ** c **and

*n*_{0}.**f(n) >= c*g(n)**for all

**n, n>=n0**where

**f**and

**g**are non-negative functions

**g(n) is an lower-bound on the value of f(n)**

Example: |
|||

f(n) | T(P) | ||

3n+2
10n2 +4n+2 6*2n + n2 |
Ω(n)
Ω(n2) Ω(2n) |
3n+2 >= 3n for all n>=2
10n2 +4n+2 >= 10n2 for all n>=5 6*2n + n2 >= 6*2n for all n>=4 |

**Theta notation:**

The** f(n) = θ (g(n)) ( f(n)** is **θ** of **g(n))** iff for some constants *c1,c2 *and *n*_{0}

**c1*g(n)<= f(n) <= c*g(n)** **¥ n, n>=n _{0} **where f and g are non-negative functions g(n) is both an upper-bound and a lower-bound on the value of f(n)

It is denoted by θ.

Example: |
|||

f(n) | T(P) | ||

3n+2
10n2 +4n+2 6*2n + n2 |
θ (n)
θ (n2) θ (2n) |
3n <= 3n+2 <= 4n for all n>=2
10n2 <= 10n2 +4n+2 <= 11n2 for all n>=5 6*2n <= 6*2n + n2 <= 7*2n for all n>=4 |

**Little oh notation**

It is defined as: Let, f(n) and g(n) be the non-negative functions then** lim _{𝑛→∞} 𝑓(𝑛)/𝑔(𝑛) = 0** such that

**f(n)=o(g(n)). f(n)=o(g(n))**if and only if

**f(n)=o(g(n))**and

**f(n)≠θ (g(n))**. It is denoted as o.

**Little omega notation **

It is defined as: Let,** f(n)** and **g(n)** be the non-negative functions then **lim _{𝑛→∞} 𝑔(𝑛)/𝑓(𝑛) = 0** such that

**f(n)=Ω(g(n))**. It is denoted as

**Ω.**

Topic : **Asymptotic Notation | big O omega theta**