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