<aside> 💡 선 요약 빅 O, 오메가, 세타 정의와 성질 삽입, 머지 소트 분석하기

</aside>

Asymptotic Bounds

Big O notation (상계)

$$ $f(n) ~is~ O(g(n))$

$↔ \exist c >0 , n_0 ≥0~ s.t. ~f(n) ≤ c * g(n)~ for~ all~ n>n_0$

ex. show that n+200 is O(n^2)

pf. for c=1, n^2-n+200 > 0 for n > ~ 14.561 therefore let n0=15 QED

Big Omega Notation (하계), Big Theta Notation

Omega: f(n) ≥ c*g(n)

Theta: Omega(g(n)) and O(g(n))

Properties

• Transitivity
  • f=O(g), g=O(h) → f=O(h)
  • 오메가와 세타에 대해서도 성립
• Additivity
  • f=O(h), g=O(h) → f+g = O(h)
  • 오메가와 세타에 대해서도 성립
• Common Rules
  • 계수는 제거될 수 있다 (ex. 14n^2 → n^2 취급)
  • 최고차항만 고려해도 된다.
  • exp 가 있으면 polynomial을 무시해도 되고 polynomial이 있으면 log를 무시해도 된다.

Examples

• polynomial