# DAA : Asymptotic Notations

Updated: Dec 6, 2019

**Asymptotic Notations**

Asymptotic notation is a way of comparing functions that ignores constant factors and small input sizes. Three notations used to compare orders of growth of an algorithm‘s basic operation count are:

**O, Ω, Θ notations **

**1. Big Oh- O notation**

**Definition**: A function t(n) is said to be in O(g(n)), denoted **t(n)=O(g(n))**, if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some nonnegative integer n0 such that

**t(n) ≤ cg(n) for all n ≥ n0**

**2. Big Omega- Ω notation**

**Definition**: A function t (n) is said to be in Ω (g(n)), denoted** t(n) =Ω(g (n) )**, if t (n) is bounded below by some constant multiple of g (n) for a ll large n, i.e., if there exist some positive constant c and some nonnegative integer n0 such that

**t(n) ≥ cg(n) for all n ≥ n0**

### 3. Big Theta - Θ notation

**Definition:** A function t (n) is said to b e i n Θ(g (n)), denoted **t(n) =Θ(g (n))**, if t (n) is bounded both above a nd below by some constant multiple of g (n) for all large n, i.e., if there exist some positive constant c1 and c2 and some nonnegative integer n0 such that

** c2 g (n) ≤ t (n) ≤ c1 g (n) for all n ≥ n0 **