程序代写代做代考 algorithm graph COMP 250

COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 6-3 : Asymptotic Notation 2
Giulia Alberini, Fall 2020

WHAT ARE WE GOING TO DO IN THIS VIDEO?
Properties of Asymptotic notations  Big-Omega, Ω(⋅)
 Big-Theta, Θ(⋅)

RULES OF BIG-OH
 Scaling Sum rule Product Rule  Transitivity

SCALING
For all constant factors 𝑎 > 0,
if 𝑓(𝑛) is O 𝑔 𝑛 , then 𝑎 ⋅ 𝑓(𝑛) is also 𝑂 𝑔 𝑛 .
(This rule is obvious if you understand the definition of big 𝑂)

SCALING
For all constant factors 𝑎 > 0,
if 𝑓(𝑛) is O 𝑔 𝑛 , then 𝑎 ⋅ 𝑓(𝑛) is also 𝑂 𝑔 𝑛 .
Proof: By definition, if 𝑓 𝑛 is 𝑂 𝑔 𝑛 then there exist two positive constants 𝑛0 and 𝑐 such that, for all 𝑛 ≥ 𝑛0 ,
𝑓𝑛≤𝑐𝑔𝑛.
Thus, …?

SCALING
For all constant factors 𝑎 > 0,
if 𝑓(𝑛) is O 𝑔 𝑛 , then 𝑎 ⋅ 𝑓(𝑛) is also 𝑂 𝑔 𝑛 .
Proof: By definition, if 𝑓 𝑛 is 𝑂 𝑔 𝑛 then there exist two positive constants 𝑛0 and 𝑐 such that, for all 𝑛 ≥ 𝑛0 ,
Thus,
𝑓𝑛≤𝑐𝑔𝑛.
𝑎⋅𝑓𝑛≤𝑎𝑐𝑔𝑛
This constant satisfies the definition that 𝑎 ⋅ 𝑓 𝑛 is 𝑂 𝑔 𝑛

SUM RULE
If𝑓(𝑛)isO𝑔𝑛 and𝑓(𝑛)isO𝑔𝑛,then𝑓𝑛+𝑓𝑛isO𝑔𝑛. 1212
Proof: …

SUM RULE
If𝑓(𝑛)isO𝑔𝑛 and𝑓(𝑛)isO𝑔𝑛,then𝑓𝑛+𝑓𝑛isO𝑔𝑛. 1212
Proof: Let 𝑛1, 𝑐1 and 𝑛2, 𝑐2 be constants such that
𝑓 𝑛 ≤ 𝑐 𝑔(𝑛) for all 𝑛 ≥ 𝑛 and 𝑓 𝑛 ≤ 𝑐 𝑔(𝑛) for all 𝑛 ≥ 𝑛 111222

SUM RULE
If𝑓(𝑛)isO𝑔𝑛 and𝑓(𝑛)isO𝑔𝑛,then𝑓𝑛+𝑓𝑛isO𝑔𝑛. 1212
Proof: Let 𝑛1, 𝑐1 and 𝑛2, 𝑐2 be constants such that
𝑓 𝑛 ≤ 𝑐 𝑔(𝑛) for all 𝑛 ≥ 𝑛 and 𝑓 𝑛 ≤ 𝑐 𝑔(𝑛) for all 𝑛 ≥ 𝑛
111222
Then,
So, 𝑓 𝑛 + 𝑓 𝑛 ≤ (𝑐 +𝑐 ) 𝑔(𝑛) for all 𝑛 ≥ max( 𝑛 , 𝑛 )
121212
These constants satisfy the big 𝑂𝑂 definition

SUMRULE (MOREGENERAL)
If𝑓(𝑛)isO 𝑔 𝑛 and𝑓(𝑛)isO 𝑔 𝑛 , 1122
Then𝑓 𝑛 +𝑓 𝑛 isO𝑔 𝑛 +𝑔(𝑛). 1212
Proof: Try it!

PRODUCT RULE
If𝑓(𝑛)isO𝑔 𝑛 and𝑓(𝑛)isO𝑔 𝑛 ,then𝑓 𝑛 ∗𝑓 𝑛 isO𝑔 𝑛 ∗𝑔 𝑛 . 11221212
Proof: …

PRODUCT RULE
If𝑓(𝑛)isO𝑔 𝑛 and𝑓(𝑛)isO𝑔 𝑛 ,then𝑓 𝑛 ∗𝑓 𝑛 isO𝑔 𝑛 ∗𝑔 𝑛 . 11221212
Proof: Let 𝑛1, 𝑐1 and 𝑛2, 𝑐2 be constants such that
𝑓 𝑛 ≤ 𝑐 𝑔 (𝑛) for all 𝑛 ≥ 𝑛 and 𝑓 𝑛 ≤ 𝑐 𝑔 (𝑛) for all 𝑛 ≥ 𝑛 111 1222 2

PRODUCT RULE
If𝑓(𝑛)isO𝑔 𝑛 and𝑓(𝑛)isO𝑔 𝑛 ,then𝑓 𝑛 ∗𝑓 𝑛 isO𝑔 𝑛 ∗𝑔 𝑛 . 11221212
Proof: Let 𝑛1, 𝑐1 and 𝑛2, 𝑐2 be constants such that
𝑓 𝑛 ≤ 𝑐 𝑔 (𝑛) for all 𝑛 ≥ 𝑛 and 𝑓 𝑛 ≤ 𝑐 𝑔 (𝑛) for all 𝑛 ≥ 𝑛
111 1222 2
Then,
So, 𝑓 𝑛 ∗𝑓 𝑛 ≤ 𝑐 𝑐 𝑔 𝑛 ∗𝑔 𝑛 forall 𝑛 ≥max(𝑛 ,𝑛 )
121212 12
These constants satisfy the big 𝑂 definition

TRANSITIVITY RULE
If𝑓(𝑛) is O 𝑔 𝑛 and 𝑔(𝑛)isO h 𝑛 ,then…?

TRANSITIVITY RULE
If𝑓(𝑛)isO𝑔𝑛 and𝑔(𝑛)isOh𝑛 ,then𝑓𝑛 is𝑂h𝑛 .

TRANSITIVITY RULE
If𝑓(𝑛)isO𝑔𝑛 and𝑔(𝑛)isOh𝑛 ,then𝑓𝑛 is𝑂h𝑛 .
Proof: Let 𝑛1, 𝑐1 and 𝑛2, 𝑐2 be constants such that
𝑓 𝑛 ≤ 𝑐1 𝑔(𝑛) for all 𝑛 ≥ 𝑛1 and 𝑔 𝑛 ≤ 𝑐2 h(𝑛) for all 𝑛 ≥ 𝑛2

TRANSITIVITY RULE
If𝑓(𝑛)isO𝑔𝑛 and𝑔(𝑛)isOh𝑛 ,then𝑓𝑛 is𝑂h𝑛 . Proof: Let 𝑛1, 𝑐1 and 𝑛2, 𝑐2 be constants such that
𝑓 𝑛 ≤ 𝑐1 𝑔(𝑛) for all 𝑛 ≥ 𝑛1 and 𝑔 𝑛 ≤ 𝑐2 h(𝑛) for all 𝑛 ≥ 𝑛2 Then,
𝑓 𝑛 ≤ 𝑐1 𝑐2 h(𝑛) for all 𝑛 ≥ max(𝑛1,𝑛2) These constants satisfy the big 𝑂 definition

COMMON FUNCTIONS
Claim: each of the following holds for n sufficiently large
1 0,𝑏 < 0 Claim: 𝑇 𝑛 is Ω(𝑛) 𝑏𝑒𝑠𝑡 𝑇 𝑛 ISΩ𝑛 –PROOF 𝑏𝑒𝑠𝑡 Claim: 𝑇 𝑛 is Ω(𝑛) 𝑏𝑒𝑠𝑡 Proof:𝑇 𝑛 =𝑎𝑛+𝑏 𝑏𝑒𝑠𝑡 ≥𝑎𝑛+𝑏𝑛, forall𝑛≥1since𝑏<0 =𝑎+𝑏𝑛 So we can take 𝑐 = 𝑎 + 𝑏 (which is positive since it is equal to 𝑇 (1)) and 𝑛 = 1. 𝑏𝑒𝑠𝑡 0 OBSERVATION ON BEST-CASE LOWER BOUNDS  Since Ω-notation describes a lower bound, when we use it to bound the best-case running time of an algorithm, then we have a lower bound on the running time of the algorithm on every input. That is, Since𝑇𝑛 ≥𝑇 𝑛,if𝑇 𝑛 =Ω𝑔𝑛 ,then𝑇𝑛 =Ω(𝑔𝑛) 𝑏𝑒𝑠𝑡 𝑏𝑒𝑠𝑡 INSERTION SORT What do we know about the running time of insertion sort up to know? We computed 𝑇 𝑛 ,𝑇 𝑏𝑒𝑠𝑡  We have proved that 𝑇 𝑛 is𝑂𝑛2 ,and (𝑛), and 𝑇 (𝑛) 𝑤𝑜𝑟𝑠𝑡 𝑤𝑜𝑟𝑠𝑡 𝑇 𝑛isΩ𝑛 𝑏𝑒𝑠𝑡 Therefore, 𝑇(𝑛) is both 𝑂(𝑛2) and Ω(𝑛). TRY IT! Prove that the scaling, sum, product, and transitivity rules all hold for big Omega also. BACK TO THE COMMON FUNCTIONS Each of the following holds for n sufficiently large: 1