Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Asymptotic(Mathematical) Notation
• Big-Oh Notation [O]
• Omega Notation [𝝮]
• Theta Notation [𝞱]
• Little- Oh Notation [o]
• Little – Omega Notation [w]
Introduction of Algorithms
• Omega Notation [𝝮]: Ω notation provides an asymptotic lower bound.
• We write f(n) = Ω(g(n)), if there exists a positive integer n0 and a positive
constant c, such that f(n)>=c.g(n) ∀ n≥n0 (i.e. the growth rate of g(n) should
be less than or equal to f(n)).
• Example :
(1) F(n) = n2 + 2
G(n) = n3
(2) f(n) = n2 + 2
g(n) = n2 + 4
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
F(n) = 2n
G(n) = n2 +2
Introduction of Algorithms
• Theta Notation [𝞱]: 𝞱 notation provides an asymptotic equal bound.
• We write f(n) = 𝞱(g(n)), if there exists a positive integer n0 and a positive
constant c1 and c2, such that c1.g(n)<= f(n)<=c2.g(n) ∀ n≥n0 (i.e. the growth
rate of g(n) should be equal to f(n)).
• Example : which of the following can be represented in theta notation.
(1) F(n) = n2 + 2
G(n) = n3
(2) f(n) = n2 + 2
g(n) = n2 + 4
Introduction of Algorithms
f(n) = n2 + 2
g(n) = n2 + 4
n, n+1, n/2 , 2n, n-2 growth rate of all are equal.
Introduction of Algorithms
Q1. Arrange the following function on the basis of their growth rate
F(n) = 2n
G(n) = n!
H(n) = nn
Introduction of Algorithms
Q2. Which of the following is true for the following function?
f(n) = n2 + n + 1
g(n) = n2 + 1
(a) f(n) = 𝞱(g(n))
(b) g(n) = 𝞱(f(n))
(c) f(n) = Ω(g(n))
(d) g(n) = Ω(f(n))
(e) f(n) = O(g(n)
(f) g(n) = O(f(n)
Introduction of Algorithms
• little-Oh Notation [o] : The little o notation defines a strict upper bound of an
algorithm.
• Given non negative f(n) and g(n) defined on a +ve integers, we can say that f(n)
= o(g(n) if there exists a positive integer n0 and a positive constant c, such that
f(n)<c.g(n) ∀ n≥n0 (i.e. the growth rate of g(n) should be greater than f(n)).
• Example :Which of the following can be represented in little-Oh Notation
notation.
(1) F(n) = n2 + 2
G(n) = n3
(2) f(n) = n2 + 2
g(n) = n2 + 4
Introduction of Algorithms
Introduction of Algorithms
• little-Omega Notation [w] : The little w notation defines an strict lower bound
of an algorithm.
• Given non negative f(n) and g(n) defined on a +ve integers, we can say that f(n)
= w(g(n) if there exists a positive integer n0 and a positive constant c, such that
f(n)>c.g(n) ∀ n≥n0 (i.e. the growth rate of g(n) should be less than f(n)).
• Example :Which of the following can be represented in little-Omega Notation
notation.
(1) F(n) = n2 + 2
G(n) = n3
(2) f(n) = n2 + 2
g(n) = n2 + 4
Introduction of Algorithms
Introduction of Algorithms
How to check growth rate of functions?
• By putting the larger value of n : As discussed earlier.
𝑓(𝑛)
• By applying limit l𝑖𝑚𝑛→ ∞
𝑔(𝑛)
• If result is 0 then g(n) >f(n)
• If result is ∞ then f(n) > g(n)
• If result is any constant then f(n) = g(n)
• By applying Log
Introduction of Algorithms
How to check growth rate of functions?
• By putting the larger value of n : As discussed earlier.
𝑓(𝑛)
• By applying limit l𝑖𝑚𝑛→ ∞
𝑔(𝑛)
• If result is 0 then g(n) >f(n)
• If result is ∞ then f(n) > g(n)
• If result is any constant then f(n) = g(n)
• By applying Log
Introduction of Algorithms
How to check growth rate of functions?
• By putting the larger value of n : As discussed earlier.
𝑓(𝑛)
• By applying limit l𝑖𝑚𝑛→ ∞
𝑔(𝑛)
• If result is 0 then g(n) >f(n)
• If result is ∞ then f(n) > g(n)
• If result is any constant then f(n) = g(n)
• By applying Log
Introduction of Algorithms
How to check growth rate of functions?
• By putting the larger value of n : As discussed earlier.
𝑓(𝑛)
• By applying limit l𝑖𝑚𝑛→ ∞
𝑔(𝑛)
• If result is 0 then g(n) >f(n)
• If result is ∞ then f(n) > g(n)
• If result is any constant then f(n) = g(n)
• By applying Log
Introduction of Algorithms
• Arrange following function in increasing order on the basis of their growth rate
• G1(n) = 2n
• G2(n) = n3/4
• G3(n) = n(logn)3
• G4(n) = nlogn
• G5(n) = n2n
• G6(n)= n!
• G7(n) = nn
2
• G8(n) = 2 n
Introduction of Algorithms
• Arrange following function in increasing order on the basis of their growth rate
• G1(n) = 2n
• G2(n) = n3/4
• G3(n) = n(logn)3
• G4(n) = nlogn
• G5(n) = n2n
• G6(n)= n!
• G7(n) = nn
2
• G8(n) = 2 n
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Properties of Asymptotic Notation :
Introduction of Algorithms
Conclusion:
Notation Reflexive Symmetric Transitive Transpose Antisymmetric Asymmetric
O Yes No* Yes O→𝝮 Yes No*
𝝮 Yes No* Yes 𝝮→O Yes No*
𝞱 Yes Yes Yes 𝞱→𝞱 Yes No
o No No Yes o→w Yes Yes
w No No Yes w→o Yes Yes
* may or may not be
41
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
Introduction of Algorithms
