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






  1. Introduction

  2. Asymptotic Notations

  3. Algorithm Design Techniques

  4. Recurrence Relation

  5. Divide and Conquer approach




© 2019 by Techy Bande Official.

Developed By : RK JAMERIA