Classifying Functions - Big oh, theta, omega

Classifying Functions

• 점근 증가율, 점근 순서. 상수나 small input은 무시하고 비교한다.
• Ω(g): big omega. lower bound. 최소 g만큼 빠르게 증가하는 함수  ex) Ω(n)이면 n+10, n^3+3 모두 해당됨
• Ω(g): big oh. upper bound. g보다 증가율이 빠르지 않은 함수 ex) Ω(n^2)이면 n^2+7, 3n+10 모두 해당됨
• Θ(g): big theta. g와 같은 비율로 증가하는 함수.  Ω(g)∩Ω(g)
• Little oh, little omega: big oh, big omega에서 증가율이 같은 경우는 제외한 것

Big oh, theta, omega의 특성

  1. Transitive(전이성): f∈O(g)이고 g∈O(h)면 f∈O(h)

  2. Reflexive(반사성): f∈Θ(f)

  3. Symmetric(대칭성): Θ 라면, g∈Θ(f)

    위의 세 가지 특성을 만족하면 Equivalence relation이다. Big theta는 함수에 대해 equivalence relation을 결정.

  4. f∈O(g) <=> g∈Ω(f)   (g의 증가율>=f의 증가율)

  5. O(f+g) = O(max(f,g))

 

Examples

• O(1): 인풋사이즈와 관계없이 일정한 연산
• f∈Θ(n): f는 linear
• f∈Θ(n^2): f는 quadratic
• f∈Θ(n^3): f는 cubic
• lg n ∈ o(n^a) for any a>0, including fractional powers
• n^k ∈ o(c^n) for any k>0, any c>1