DAA : Asymptotic Notations

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

1. Introduction

2. Asymptotic Notations

3. Algorithm Design Techniques

4. Recurrence Relation

5. Divide and Conquer approach