Data Science
& AI
Algorithms
Analysis of Algorithms
Lecture No.- 06 By- Aditya sir
Recap of Previous Lecture
Topic Maths Properties
Topic Big Notations with Examples
Topic to Small Hotations
Intro
Topics to be Covered
Topic Small Hotations
0 w
Topic
Problem Solving
Topic
Examples Venn
diagram
7m
10h
7,2
575 8
10h 55 8
7m
5nlogn 3h42 3n t2
7,3 2
3h42
5nlogn 7m 2n
I
01m sin
IN 01m and
4 RCN
Small 0h o
Ledpper Bound
that fin 019 n1 iff
we say
for all 270 strictly
fin 2CA.ge less
when our n no
all some no 70
for
4
Bigohvssmalloh
i.FM
3Mt 2 SOM
3 2 ion
fin O n
37 2 o n
3n 2 CAN
B 103
3h 2 2n Oln is
3h42 n
Tight VI
39 2 0.50 608312
4
eg fin n nts 01m
fin 0 n3
01m Tight UB
01m
p3 10050 OBV
nrnan nr
his
4
nrn v5 m
non is n
log both sides
Mrn n Taking
log n2
log nra
in n
112
log n log n
log n log n2
log at
5
log D2
1.5 IN 2109h
4
t.sc
Small w lower Bound
Omega be
that Fin w gin IFF
we say
fin CA whenever
for all 270 g n
n no
all for some
strictly
not
4
Big Omega vs Small Omega
some
Fin 50 2
DID
5 27 2n 5n 2 A n
59 2 1in 11h
I 1m
w 1m
5 27 on
w rn
In 2 100 7 not w s
59 2 7700N to
CB
4
w n
Tight
9 Is n W
Yn Tom
all do
n
at for
TI
is
1 1 Fake
no
rate of growth Take large values
no
of
D linear Pres
4
Yn linearly ders
Incisions Truffalle
21
NO 0 2n
2 0 2n
nb
If o2azb then n 0 Toy
24 Oln
4
2
1 2
SEEK an an_ admin
i 1am amen
way
22h 8 2
227 2
21 2
2
122
a 24 4 2
2n 7 1
4
both sides
wayfi Taking log on
22h 2
1091227 10912
an
n
look
2n
n
mathemfally
4
2
Doubt 2 22 22 22
I
uth
amn amx.am amtan
THE
1
24 0 an
2 2
2 2
4
ocacb then n nb
0
11
n an Comparing
polynomials
a b
of diff
degrees
Tnb
4
21m Oln
n
2
2m n
n
DO
we know
2 n n 0 12m
Take log
2m O n
log 2m log nn 2
m
n
logn
n logh
5
n logn
Asymptotic Comparison
Imptype i
Enkidu the following functions
10 Thin 1097
The correct arrangement of these functions
complexity
in increasing order of asymptotic
is
10 rn
A logg 10mn B
loggin
10 login r n D 1099,10 man
5
Deer D
Approach
const C
10 r n 1091 Log 5L
P
poly
E
EXPO
e
p
In general I
C 2 L L P E
D
co log CI ct
rich
5 n 12 n
IMDB.us ns
Tweak
is yn T
log n
0 T
20th logn nlogn
k some k
I
In c 0 nk for n nts
m is O 2409 False
D is O 213109
TIL
5
logn O log log n Fate
antolndforaslinn.ee
logn Yn
logn C
D
d
log
True
5
2ox nx
logn O n
log n
TIM
25
2onlogn CA n on
False
n c nk
eg
2
1
Polynomial of degree
n 1
K
In 533m
oink
5
n
1
0 2109m False
both sides
log
Taking
m
allogn
21097
log m
2
log 2
m 2192
2092 logs
n 1121097
loght toga
1 m 012109h
5 logn y
O 22109h
m
m 22109h
m 221099
sides 01221097
log both
Taking
and here
22109h
109,1m log 2
10
2 1091 2109h
5 IzloginalogT
2
logn Of log loans
log n log log n
142 both
log sides
ways Let logn n Taking
log flogn log log logs
2 log a
lagoon logogcogns
w̅ age Let 109 logs n
5 V10 loan In loga
An O n 10
91
an EXPO EXPO 0 Poly
n
Poly
Em
eg a 2
Poly CA Expo Poly O Expo
EXPO Poly
5
IryPty
Does Asymptotic Notations follow
Tricotomy Property
HI
5
Por Real nos
Tricotomy Property
Given any two real numbers nly fixed
Then a
y follow exactly one
of
the below relation
5 y
1 N
y eg.in 7
2
nsy may
OR 3
MY
5
Tricotomy Property in Asymptotic Comparison
2 functions
of n
F n
g
Given 2 positive functions
does Fin and g n always follow
the below
exactly one
of
F R 9
1 Fln g n
co g
2 FIN 9 n f 019
g
OR 3 Fin 9 D
5 f 019 or
9 0 F
Q fin 5m
9 n 7m
f
49
7m
f n 0 gin
5m
and
almans for Fcn glut
nano
5
fin 5m
192
gen
f R
5h27
alveeny for 9 wcg
Sme nano
5
Fln 10m 7
193 f
9in 5m 12
both how equal
Asymptotically
rate of growth
Fln 0191ns
FED
and Ñ
5
fin n n.n vasi ab.es
egg
9in plitsina
Sinn plot 1 I
war
in
5
fin n
9in plitsinn
fin n
gal m
Eli Sinn I
n n
FIN n
1 1
t.LI
9 n
n F 019
n2
or
5 F o g
Erez Sinn I
fln n g n 1
fin n
const
sinn
gen n
mean
fm
gmD
n I f g
or
F w g
5
Imp observation from poor egi
f n n
it Sinn
9 n n
hoidifu
fff
al 9in are not
the tricotomy property
as we can't get a clear
asymptotic comparison
between both uneven nano
5
Conclusion
or
Hotations may
Asymptotic
property
may
not
follow Tricotomy
H
Tricotomy property does not Hold
Notations
for Asymptotic
5
2 mins Summary
Topic Small Hotations 0 co
Topic Imp Questions
Tricotomy Property
Topic
Topic
p
THANK - YOU
Telegram Link:
https://t.me/AdityaSir_PW
