$\theta-notation$

$f(n) = \theta(g(n)) \approx f(n) = g(n)$ in degree

• Asymptotic tight bound

  • $f(n) = \theta(g(n))$

    • $0 \le c_1g(n) \le f(n) \le c_2g(n)$ for all $n_0 \le n$
    • $n_0 \le n$인 모든 양수 n에 대해 위 조건을 만족시키는 양수 $c_1$과 $c_2$가 존재하는 경우

$O-notation$

$f(n) = \theta(g(n)) \approx f(n) \le g(n)$ in degree

• Upper bound
  • g(n) is an upper bound of f(n): g(n)이 실수 전체 n에 대해 f(n) 보다 작다.

• Asymptotic upper bound
  • $f(n) = O(g(n))$
    • $0 \le f(n) \le cg(n)$ for all $n_0 \le n$
    • $n_0 \le n$인 모든 양수 n에 대해 위 조건을 만족시키는 양수 c가 존재하는 경우

$\Omega-notation$

$f(n) = \theta(g(n)) \approx f(n) \le g(n)$ in degree

• Asymptotic lower bound

  • $f(n) = \Omega(g(n))$

    • $0 \le cg(n) \le f(n)$ for all $n_0 \le n$
    • $n_0 \le n$인 모든 양수 n에 대해 위 조건을 만족시키는 양수 c가 존재하는 경우

Asymptotic notation

Asymptotic notation에서 c와 $n_0$를 찾기 위해서 각 변을 $n_d$(d는 차수)로 나누고 n=1부터 대입한다.

일반적으로 $p(n) = \displaystyle\sum_{i=0}^{d} a_in^i$ 은 $p(n) = \theta(n^d)$ 이다.

추가적인 Asymptotic notation

$o-notation$

$f(n) = o(g(n)) \approx f(n) < g(n)$

$omega-notation$

$f(n) = \omega(g(n)) \approx f(n) > g(n)$

Time-complexity of sorting algorithm

알고리즘	최선의 경우 (Best Case)	최악의 경우 (Worst Case)
Insertion Sort	Θ(n)	Θ(n²)
Selection Sort	Θ(n²)	Θ(n²)
Merge Sort	Θ(n log n)	Θ(n log n)
Binary Search	Θ(1)	Θ(log n)

Comparision of functions

f(n) and g(n) are asymptotically positive (n이 충분히 클 때, 양수)라고 가정하자

Transitivity (=,≤,≥,<,>)

1. $(f(n) = \Theta(g(n))$ and $(g(n) = \Theta(h(n))$ imply $(f(n) = \Theta(h(n))$

2. $f(n) = O(g(n)))$ and $(g(n) = O(h(n)))$ imply $(f(n) = O(h(n)))$

3. $(f(n) = \Omega(g(n)))$ and $(g(n) = \Omega(h(n)))$ imply $(f(n) = \Omega(h(n)))$

4. $(f(n) = o(g(n)))$ and $(g(n) = o(h(n)))$ imply $(f(n) = o(h(n)))$

5. $(f(n) = \Theta(g(n)))$ and $(g(n) = \Theta(h(n)))$ imply $( f(n) = \Theta(h(n)))$

Reflexivity (=,≤,≥)

1. $( f(n) = \Theta(f(n)) )$
2. $( f(n) = O(f(n)) )$
3. $( f(n) = \Omega(f(n)) )$

Symmetry (=)

1. $( f(n) = \Theta(g(n)) )$ if and only if $( g(n) = \Theta(f(n)) )$

Transpose symmetry (≤↔≥, <↔>)

1. $( f(n) = O(g(n)) )$ if and only if $( g(n) = \Omega(f(n)) )$
2. $( f(n) = o(g(n)) )$ if and only if $( g(n) = \omega(f(n)) )$

Trichotomy

어떤 실수 a, b에 대하여, a<b, a=b, a>b 중 하나는 반드시 성립한다.

• 어느 두 숫자는 반드시 비교가 가능하다.

두 함수가 항상 asymptotic comparable 할까?

f(n) ≠ O(g(n)) & f(n) ≠ Ω (g(n))이 가능할까?

1. f(n) = n, g(n) = $n^{1 + \sin(n)}$ 이라고 가정하자.
2. $-1 \le1 + \sin(n) \le 1$ 이기 때문에 $n^0 \le n^{1 + \sin(n)} \le n^2 이다.$
3. (2)에 따라 $n^{1 + \sin(n)}$ 는 진동하기 때문에 특정 구간에서 비교가 불가능 하다.
4. 따라서 f(n) ≠ O(g(n)) & f(n) ≠ Ω (g(n))이 가능한 경우가 있다.