Date : 22-01-2024
================
ASYMPTOTIC NOTATION
Asymptotic notation gives time needed by an algorithm as a function of input size .
Asymptotic notations [ O , Ω , Θ , o , ω ]
Big-Oh notation ( O ):
Let f(n) and g(n) are two non-negative functions
The function f(n) = O(g(n)) iff there exists two positive c >0 and n0 ≥ 1
such that f(n) ≤ c.g(n) for all n≥ n0
Eg 1:
f(n)=n2; g(n)=2n
f(n) = O(g(n))
f(n) ≤ c.g(n)
c=1 n0=4
n n2 2n
1 1 2
2 4 4
3 9 8
4 16 16
5 25 32
6 36 64
7 49 128
8 64 256
.
.
.
n2 = O(2n)
(c, n0)=(1,4)
(2,4)
(3,4)
Eg 2:
f(n)=n2; g(n)=n
f(n) = O(g(n))
f(n) ≤ c.g(n)
n2 ≤ c. n
f(n)≠ O(g(n))
Eg 3:
f(n) =3n+1; g(n)= n2+2
f(n) = O(g(n))
f(n) ≤ c.g(n)
c=1; n0=3
n 3n+1 n2+2
1 4 3
2 7 6
3 10 11
4 13 18
5 16 27
6 19 38
Eg 4:
f(n) = 2n ; g(n)=20n
f(n) = O(g(n))
f(n) ≤ c.g(n)
c=1; n0=1
n 2n 20n
1 2 20
2 4 40
3 6 60
.
.
Conclusions:
1). Drop lower order terms
2). Ignore constants
Eg 5:
f(n) = 2n+1; g(n) =n
f(n) = O(g(n))
f(n) <= c . g(n)
c=3 ; n0=1
n f(n)=2n+1 g(n)=3n
________________________
1 3 3
2 5 6
3 7 9
4 9 12
Date : 23-01-2024
================
Eg 6:
f(n)=logn; g(n)=2n
f(n) = O(g(n))
f(n) ≤ c.g(n)
c=1; n0=1
n logn 2n
1 0 2
2 1 4
4 2 8
8 3 16
16 4 32
Knowledge Explore:
Q 1:
f(n) =n; g(n)=2n2 ; h(n) =30logn
Q2:
f(n)= 2n; g(n)= 3n
Q 3:
Arrange the following in ascending order of growth rate
F1(n) = logn ; f2(n) = loglogn ; f3(n) =3n2 ; f4(n) =100n+20; f5(n) =100nlogn
Date : 26-01-2024
================
Big-Omega notation ( Ω ):
Let f(n) and g(n) are two non-negative functions
The function f(n) = Ω (g(n)) iff there exists two positive c >0 and n0 ≥ 1
such that f(n) ≥ c.g(n) for all n≥ n0
Eg 1:
f(n) = n2 ; g(n) =n
f(n) = Ω (g(n))
f(n) ≥ c.g(n)
n2 ≥ c. n
(c, n0)
(1,1)
n2 = Ω (n)
Eg 2:
f(n)=n; g(n)= n2
f(n) = Ω (g(n))
f(n) ≥ c.g(n)
n ≥ c. n2
1≥c.n
c.n ≤ 1
1
n≤
c
n ≠ Ω (n2)
Conclusions:
1). ( f(n) = O (g(n)) ) ↔ ( g(n) = Ω (f(n)) )
2). ( f(n) ≠ O (g(n)) ) ↔ ( g(n) ≠ Ω (f(n)) )
Eg 3:
f(n)= 22n;g(n)= 2n ;
f(n) = Ω (g(n))
f(n) ≥ c.g(n)
22n ≥ c . 2n
22n
___
≥c
2n
2n ≥ c
c ≤ 2n
c=1,n0=1
f(n) = Ω (g(n))
Theta notation ( Θ ):
Let f(n) and g(n) are two non-negative functions
The function f(n) = Θ (g(n)) iff there exists positive constants c 1>0 , c2>0 and n0 ≥ 1
such that c1. g(n) ≤ f(n) ≤ c2.g(n) for all n≥ n0
Eg 1:
f(n)=3n+3 ; g(n)=100n+2
f(n) = Θ (g(n))
c1. g(n) ≤ f(n) ≤ c2.g(n)
f(n) ≤ c2.g(n)
3n+3 ≤ c2. (100n+2)
c2.=1
3n+3 ≤ 100n+2
1 ≤ 97n
n ≥ 1/97
n0=1
c1. g(n) ≤ f(n)
c1 (100n+2 ) ≤ (3n+3)
c1=1/100; n0=1
Big-Oh Notation(O):
n2 = O(n2) => Tightest Upper bound
= O(n3) => Non-Tightest Upper bound
= O(n10) => Non-Tightest Upper bound
≠ O(n) => Not an Upper bound
Small-oh Notation(o):
Non-tightest upper bounds
n2 = o(n3) => Non-tightest Upper bound
= o(n5) => Non-tightest Upper bound
≠ o(n) => Not an Upper bound
≠ o(n2) => Tightest Upper bound
Big-Omega Notation(Ω):
n3 = Ω (n3) => Tightest Lower bound
= Ω (n2) => Non-tightest Lower bound
=Ω (n) => Non-tightest Lower bound
≠ Ω (n4) => Not a lower bound
Small-Omega Notation(ω):
Non-tightest lower bounds
n3 = ω (n2) => Non-tightest Lower bound
= ω (n) => Non-tightest Lower bound
≠ω (n3) => Tightest Lower bound
≠ ω (n4) => Not a lower bound
Theta Notation (Θ):
n3 = O(n3) => Tightest Upper Bound
and
n3 = Ω (n3) => Tightest Lower Bound
=> n3 = Θ (n3) (TUB and TLB)
PRACTICE QUESTIONS
Q1:
True/False
1). n= O(n2) [True]
2). n=O(n) [True]
3). n= O(n2-10) [True]
4). n4 = O (n3) [False]
5). n2 = Ω(n) [True]
6). n= Ω(n) [True]
7). n= Ω(n2) [False]
8). Ω(n2)= Ω(n2 –10) [True]
9). n= Θ(n) [True]
10). n2= Θ(n) [False]
11). n3= Θ(n3) [True]
12) . n= Θ ( n2 –10 ) [False]
13). n= o(n2) [True]
14). n=o(n) [False]
15) . n2= o(n3) [True]
16). n2=o(n2-10) [False]
17). n2= ω(n) [True]
18). n= ω(n) [False]
19). n3= ω(n2) [True]
20). n2= ω(n2-10) [False]
TYPES OF ANALYSIS
Worst case analysis:
57 , 12 , 43 , 68 , 26 , 35
WC= Ω(n2)
