CS212: Design & Analysis of Algorithms 3rd Semester
Lecture 2: August 5
Instructor: Prof. Prateek Vishnoi Indian Institute of Technology, Mandi
W hat is the neat & and precise way to def ine the time complexity ? ?
Asymptotic notations
Big-oho(O) notation
Definition 2.1 Let f (n) and g(n) be positive function in n. f (n) is said to be order of g(n) if there exist a
positive constant c and n0 ∈ N such that for all n ≥ n0 ,
f (n) ≤ c.g(n)
We call f (n) is order of g(n) and write it as,
f (n) = O(g(n))
Examples
20n2 = O(n2 ) c = 20, n0 = 1
100n + 60 = O(n2 ) c = 1, n0 = 160
100n + 60 = O(n) c = 160, n0 = 1
n2 = O(n3 ) c = 1, n0 = 1
1000 = O(1) c = 1000, n0 = 1
2-1
2-2 Lecture 2: August 5
Some Observations
If f (n) = O(g(n)) and g(n) = O(h(n)), then
f (n) = O(h(n))
If f (n) = O(h(n)) and g(n) = O(h(n)), then
f (n) + g(n) = O(h(n))
Prove the above observations from your own.
Judgement question
Let f (n) = 3n and g(n) = 2n . Is the below statement True ?
f (n) = O(g(n))
Note : Prove or disprove from your own.
Big Omega(Ω) notation
Definition 2.2 Let f (n) and g(n) be a positive function in n. f (n) is said to be omega of g(n) if there exist
a positive constant c and n0 ∈ N such that for all n ≥ n0 ,
f (n) ≥ c.g(n)
We call f (n) is omega of g(n) and write it as,
f (n) = Ω(g(n))
Examples
20n2 = Ω(n2 ) c = 1, n0 = 1
100n + 60 = Ω(n) c = 1, n0 = 1
100n2 + 60 = Ω(n) c = 1, n0 = 1
2
n
4 = Ω(n2 ) c = 1/8, n0 = 1
1000 = Ω(1)
Lecture 2: August 5 2-3
Some Observations
If f (n) = Ω(g(n)) and g(n) = Ω(h(n)), then
f (n) = Ω(h(n))
If f (n) = Ω(h(n)) and g(n) = Ω(h(n)), then
f (n) + g(n) = Ω(h(n))
Prove the above observations from your own.
Judgement question
Let f (n) = 2n and g(n) = 3n . Is the below statement True ?
f (n) = Ω(g(n))
Note : Prove or disprove from your own.
Big Theta(Θ) notation
Definition 2.3 Let f (n) and g(n) be positive function in n. f (n) is said to be theta of g(n) if there exist a
positive constant c1 , c2 and n0 ∈ N such that for all n ≥ n0 ,
c1 .g(n) ≤ f (n) ≤ c2 .g(n)
We call f (n) is theta of g(n) and write it as,
f (n) = Θ(g(n))
Keypoint : f (n) = Θ(g(n)) if and ony if f (n) = Ω(g(n)) and f (n) = O(g(n))
2-4 Lecture 2: August 5
Small o Notation
Small o notation, denoted as o(g(n)), provides a stricter form of comparison between functions.
Definition 2.4 Let f (n) and g(n) be positive function in n. A function f (n) is said to be o(g(n)) if for
every positive constant c, there exists a positive integer n0 such that:
f (n) < c.g(n)
for all n > n0 .
Intuitive Understanding
Stricter Bound: While Big O notation O(g(n)) means that f (n) is eventually bounded above by a
constant multiple of g(n), small o notation means that f (n) grows strictly slower than g(n).
Upper Bound, Not Tight: If f (n) = o(g(n)), then f (n) grows at a rate that is asymptotically less
than g(n).
Example
f (n) = n and g(n) = n2
f (n) = o(g(n)) because for any positive constant c, there exists a sufficiently large n0 such that n < cn2
for all n > n0 .
Formal Usage
When we write f (n) = o(g(n)), it implies:
f (n)
lim =0
n→∞ g(n)
This means that the ratio of f (n) to g(n) approaches 0 as n goes to infinity, indicating that f (n) grows more
slowly than g(n).
Small Omega Notation
Small omega notation, denoted as ω(g(n)).
Definition 2.5 Let f (n) and g(n) be positive function in n. A function f (n) is said to be ω(g(n)) if for
every positive constant c, there exists a positive integer n0 such that:
f (n) > c · g(n)
for all n > n0 .
Lecture 2: August 5 2-5
Intuitive Understanding
Stricter Bound: While Big Omega notation Ω(g(n)) means that f (n) is eventually bounded below
by a constant multiple of g(n), small omega notation means that f (n) grows strictly faster than g(n).
Lower Bound, Not Tight: If f (n) = ω(g(n)), then f (n) grows at a rate that is asymptotically
greater than g(n).
Example
f (n) = n2 and g(n) = n
f (n) = ω(g(n)) because for any positive constant c, there exists a sufficiently large n0 such that
n2 > c · n for all n > n0 .
Formal Usage
When we write f (n) = ω(g(n)), it implies:
f (n)
lim =∞
n→∞ g(n)
This means that the ratio of f (n) to g(n) approaches infinity as n goes to infinity, indicating that f (n) grows
faster than g(n).
Is it possible to compare every two positive functions f (n) and g(n) asymptotically??
Analyse the functions f (n) = n and g(n) = n1+sin n
Useful fact : Stirling’s approximation(for large value of n)
√ n n
n! ≈ 2πn
e
Practice Problems
1. Prove the following :
n! = o(nn )
n! = ω(2n )
log(n!) = Θ(n log n)
2. Is 2n+1 = O(2n )? Is 22n = O(2n )? Prove or disprove.
√
3. Let f (n) = 10n , g(n) = nlog n , h(n) = n n
. Find the increasing asymptotic growth rate.
