Asymptotic notation

-> 알고리즘이 얼마나 효율적인지 따져보기 위함 !

 

0. 정리

(최고 차항만 비교하면 됨)

𝑂(𝑔) = g가 upper bound / worst case !

Θ(𝑔) = tight bound

Ω(𝑔) = g가 lower bound / best case !

 

1. O-natation  (𝑂(𝑔)=f)

-def : g(n) is asymptotic upper bound of f(n)

=

 

 

-ex (proof)

걍 pdf보기로함