# Algorithm Chapter 3 - Growth of Functions

## Asymptotic notation

### $O$-notation

> Figure 1. 圖中比較上面的那個函數是 $cg(n)$， 比較下面的函數是 $f(n)$。 $g(n)$ 是 $f(n)$ 的漸進上限。
* $O(g(n)) = \{f(n): \text{there exist positive constants } c \text{ and } n_0 \text{ s.t.} 0 \leq f(n) \leq cg(n) \text{ for all } n \geq n_0\}$
* 白話文： $O(g(n))$ 是一個函數的集合，這個集合裡面的每一個函數，在參數大到某一個程度 （$n_0$） 過後，其函數值都無法超過 $g(n)$ 的某整數倍 （$c$）
* 此時，我們稱 $g(n)$ 是 $f(n)$ 的**漸進上限 (asymptotic upper bound)**
* 如果 $f(n) \in O(g(n))$， 則我們會直接寫作 $f(n) = O(g(n))$
* 舉例：以下函數都是在 $O(n^2)$ 裏面的函數
* $n^2$
* $n^2 + n$
* $n^2 + 1000n$
* $1000n^2 + 1000n$
* $n$
* $n / 1000$
* $n^{1.99999}$
* $n^2/lg(lg(lg(n)))$

### $\Omega$-notation

> Figure 2. 圖中比較下面的那個函數是 $cg(n)$， 比較上面的函數是 $f(n)$。 $g(n)$ 是 $f(n)$ 的漸進下限。
* $\Omega(g(n)) = \{f(n): \text{there exist positive constants } c \text{ and } n_0 \text{ s.t.} 0 \leq cg(n) \leq f(n) \text{ for all } n \geq n_0\}$
* 白話文： $O(g(n))$ 是一個函數的集合，這個集合裡面的每一個函數，在參數大到某一個程度 （$n_0$） 過後，其函數值都不小於 $g(n)$ 的某整數倍 （$c$）
* 此時，我們稱 $g(n)$ 是 $f(n)$ 的**漸進下限 (asymptotic lower bound)**
* 如果 $f(n) \in \Omega(g(n))$， 則我們會直接寫作 $f(n) = \Omega(g(n))$
* 舉例：以下函數都是在 $\Omega(n^2)$ 裏面的函數
* $n^2$
* $n^2 + n$
* $n^2 - n$
* $n^2 + 1000n$
* $n^2 - 1000n$
* $1000n^2 + 1000n$
* $n^3$
* $n^{2.00001}$
* $n^2/lg(lg(lg(n)))$
* $2^{2^n}$

### $\Theta$-notation

> Figure 3. 圖中的函數由上到下是 $c_2g(n)$， $f(n)$ 和 $c_1g(n)$。 $g(n)$ 是 $f(n)$ 的漸進上下限。
* $\Theta(g(n)) = \{f(n): \text{there exist positive constants } c_1, c_2 \text{ and } n_0 \text{ s.t.} 0 \leq c_1g(n) \leq f(n) \leq c_2g(n) \text{ for all } n \geq n_0\}$
* 白話文： $O(g(n))$ 是一個函數的集合，這個集合裡面的每一個函數，在參數大到某一個程度 （$n_0$） 過後，其函數值都會介於 $g(n)$ 的某整數倍 （$c_1$） 到另一個整數倍 （$c_2$） 之間
* 此時，我們稱 $g(n)$ 是 $f(n)$ 的**漸進上下限 (asymptotic tight bound)**
* 如果 $f(n) \in \Theta(g(n))$， 則我們會直接寫作 $f(n) = \Theta(g(n))$
* $f(n) = \Theta(g(n))$， 若且唯若 $f(n) = O(g(n)) \land f(n) = \Omega(g(n))$

### $o$-notation

* $o(g(n)) = \{f(n): \text{for all positive constants } c > 0 \text{, there exists a constant } n_0 > 0 \\\text{ such that } 0 \leq f(n) < cg(n) \text{ for all } n \geq n_0\}$
* 白話文： $o(g(n))$ 是一個函數的集合，無論 $g(n)$ 乘上哪一個正數 （$c$），這個集合裡面的每一個函數總是會從某個數字開始 （$n_0$），其函數值永遠都小於（沒有等於） $cg(n)$
* 更好懂的版本： $\displaystyle{\lim_{x \to \infty}} \frac{f(x)}{g(n)} = 0$
* 舉例：以下函數都是在 $o(n^2)$ 裏面的函數
* $n^{1.9999}$
* $\frac{n^2}{lg(n)}$
* 舉例：以下函數都**不是**在 $o(n^2)$ 裏面的函數
* $n^2$
* $\frac{n^2}{1000}$

### $\omega$-notation

* $\omega(g(n)) = \{f(n): \text{for all positive constants } c > 0 \text{, there exists a constant } n_0 > 0 \\\text{ such that } 0 \leq cg(n) < f(n) \text{ for all } n \geq n_0\}$
* 白話文： $o(g(n))$ 是一個函數的集合，無論 $g(n)$ 乘上哪一個正數 （$c$），這個集合裡面的每一個函數總是會從某個數字開始 （$n_0$），其函數值永遠都大於（沒有等於） $cg(n)$
* 更好懂的版本： $\displaystyle{\lim_{x \to \infty}} \frac{f(x)}{g(n)} = \infty$

## Asymptotic notation in equations

略。

## Comparisons of functions

### Relational properties

* 遞移性 (Transitivity)
* 若 $f(n) = \Theta(g(n))$ 且 $g(n) = \Theta(h(n))$， 則 $f(n) = \Theta(h(n))$
* 於 $O$、 $\Omega$、 $o$、 $\omega$ 同理
* 自反性 (Reflexivity)
* $f(n) = \Theta(f(n))$
* 於 $O$、 $\Omega$ 同理
* 對稱性 (Symmetry)
* $f(n) = \Theta(g(n))$， 若且唯若 $g(n) = \Theta(f(n))$
* 轉置對稱性 (Transpose Symmetry)
* $f(n) = O(g(n))$， 若且唯若 $g(n) = \Omega(f(n))$
* $f(n) = o(g(n))$， 若且唯若 $g(n) = \omega(f(n))$

### Comparisons

* 若 $f(n) = o(g(n))$， 則 $f(n)$ 漸進小於 $g(n)$
* 若 $f(n) = \omega(g(n))$， 則 $f(n)$ 漸進大於 $g(n)$
* 這樣的比較是**沒有三一律**的。雖然直覺上來說，我們可能會把 $O$ 想成是 $\leq$， $\Omega$ 想成是 $\geq$， 但函數並不像一般的實數，有時候函數是無法拿來比大小的
* 例如： $n^{1+sin(n)}$ 和 $n$ 無法比大小，因為 $1 + sin(n)$ 會在 0 到 2 之間不斷振盪

## Standard notations and common functions

### Monotonicity

* 若 $m \leq n$ 時 $f(m) \leq f(n)$， 則我們說 $f(n)$ 是單調遞增 (monotonically increasing) 的函數
* 若 $m \leq n$ 時 $f(m) \geq f(n)$， 則我們說 $f(n)$ 是單調遞減 (monotonically decreasing) 的函數
* 若 $m < n$ 時 $f(m) < f(n)$， 則我們說 $f(n)$ 是嚴格遞增 (strictly increasing) 的函數
* 若 $m < n$ 時 $f(m) > f(n)$， 則我們說 $f(n)$ 是嚴格遞減 (strictly decreasing) 的函數

後面是高中數學（？？？）