Growth of Functions

Asymptotic Notation

$\Theta$-notation, $O$-notation, $\Omega$-notation 에 대해서 공부해보자

Simple Examples

• $\Theta(n^2) \neq 3n-1$
• $O(n^2) = 3n-1$
• $\Omega(n) = 3n^2-1$

$O$-notation

• Asymptotic Upper Bound
• There exist Positive constants $c$ and $n_0$ such that
  $0 \leq f(n) \leq cg(n)$ for all $n \geq n_0$

$\Omega$-notation

• Asymptotic Lower Bound
• There exist Positive constants $c$ and $n_0$ such that
  $0 \leq cg(n) \leq f(n)$ for all $n \geq n_0$

$\Theta$-notation

• Asymptotic Tight Bound
• There exist Positive constants $c_1, c_2$ and $n_0$ such that
  $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$ for all $n \geq n_0$

Examples

• Insertion sort : $O(n^2)$, $\Omega(n)$
  (= Best case : $\Theta(n^2)$, Worst case : $\Theta(n)$)
• Selection sort : $\Theta(n^2)$
• Merge sort : $\Theta(nlgn)$
• Binary search : $O(lgn)$, $\Omega(1)$

Comparison of functions

• Transitivity $(=,\leq,\geq,\lt,\gt)$ : $_aR_b,\ _bR_a \ \rightarrow \ _aR_c$
• Reflexivity $(=,\le,\ge)$ : $_aR_a$ is True
• Symmetry $(=)$ : $_aR_b \ \rightarrow \ _bR_a$
• Transpose symmetry $(\le \ \leftrightarrow \ \ge, \ \lt \leftrightarrow \gt)$ : not include '$=$'

Trichotomy (삼분)

• For any two real numbers a and b, exactly one of the following must hold
  : $a \lt b,\ a = b,\ a \gt b$,
  That is any two numbers are comparable!
• But, any two functions does not asymptotically comparable.
  : $n$ and $n^{1+sinn}$