[微積分] Little-oh 與 Big-oh 符號

一般數學分析中或者演算法分析經常會用到 $O$符號 或者 $o$符號。以下我們先引入定義。

======================
Definition: $f$ is Big-Oh of $g$
令 $f, g$ 為任意函數在 $x = x_0$ 附近可定義。我們說 當 $x \to x_0$ 時， $f(x) = O(g(x))$) 若下列條件成立：
存在 $\delta >0$ 與 正數 $c>0$ 使得\[
|x - x_0| < \delta  \Rightarrow |f(x)| \le c |g(x)|
\]======================

離散情況的Big-Oh之定義:

上述定義在離散情況也可以，亦即 $f(n)=O(g(n))$若且唯若 存在 $N \in \mathbb{N}$ 與 正數 $c>0$ 使得 對任意 $n \geq N$ 而言，$|f(n)|\leq cf(n)$。

Example: 比如說線性搜尋演算法最大執行步驟數為 $f_L(n):=4n+5$ 則不難得證 $f_L(n) = O(n)$。(hint: 取 $N=5$ 與 $C=5$即可)

Exercises: 試證 

1. $n=O(n)$, 

2. $1000n = O(n)$, 

3. $2n^3+n = O(n^3)$，

4. $0.001n^{100} = O(n^{100})$。

5. 令 $f(n) = (-1)^n$ 試證明 $f(n) = O(1)$。

Comments: $f(n) = O(1)$ 意指存在 整數 $N\in \mathbb{N}$ 與 正數 $c>0$ 使得對任意 $n\geq N$我們有 $|f(n)|\leq c \cdot 1$。此表明函數 $f$ 有上界(但不一定收斂，請看上述 exercise 5)。

======================
Definition: $f$ is Little-Oh of $g$
我們說 當 $x \to x_0$ 時， $f(x) = o (g(x))$ 若下列條件成立：
對任意 $\varepsilon>0$ 存在 $\delta > 0$  使得
\[ |x - x_0| < \delta \Rightarrow \frac{f(x)}{g(x)} < \varepsilon \]亦即上述等價為 $\displaystyle \lim_{x \to x_0} \frac{f(x)}{g(x)} = 0$
======================

Comments:
1. $o(g(x))$ (要求收斂) 條件比 $O(g(x))$ (僅要求有界) 條件強烈。

2. 我們說某函數 $f$ 在 $x_0$ 處連續亦可以用此 little-oh 符號表達：
\[
f(x) - f(x_0) = o(1) \text{ as $ x \to x_0$}
\]
3. 一般而言，上述定義中的 函數 $g(x)$ 多半考慮為較 $f(x)$ 簡單的函數以用作比較函數 decay or growth rate ；以下我們看幾個例子

Example 1: 選 $g :=1$ 且考慮當 $x \to x_0$ 時，
(a) $f(x) = O(g(x) )= O(1)$ 試解釋其意義：
(b) $f(x) = o(g(x)) = o(1)$ 試解釋其意義：

Solution：
(a) 當 $x \to x_0$ 時，$f(x) = O(g(x) = O(1)$ 由定義可知：存在 $\delta >0$ 與 正數 $c>0$ 使得\[
|x - x_0| < \delta  \Rightarrow |f(x)| \le c |1|
\]亦即 $|f(x)|$ 在 $x= x_0$ 附近有界 (在此例中此界為 $c$)

(b) 當 $x \to x_0$ 時，$f(x) = o(g(x)) = o(1)$ 由定義可知：
\[\mathop {\lim }\limits_{x \to {x_0}} \frac{{f(x)}}{{g(x)}} = \mathop {\lim }\limits_{x \to {x_0}} f(x) = 0\]


Example 2
試證明 若 $f(x) = o(x)$ 則 $\lim_{x \to 0} f(x) = 0$

Proof:
觀察
\[\mathop {\lim }\limits_{x \to 0} f(x) = \mathop {\lim }\limits_{x \to 0} \frac{{f(x)}}{x} \cdot x \;\;\;\;\; (**)
\]接著由於 $f(x) = o(x)$ 由定義可知
\[\mathop {\lim }\limits_{x \to 0} \frac{{f(x)}}{{\left| x \right|}} = 0\]且又知道
\[
\lim_{x \to 0} x =0
\]故 $(**)$ 由極限四則運算關係可得
\[\mathop {\lim }\limits_{x \to 0} f(x) = \mathop {\lim }\limits_{x \to 0} \frac{{f(x)}}{x} \cdot x = 0\]

Example 3
考慮下列數列
$$z_n:= t + o(t/n)n$$ 其中 $o(\cdot)$ 為 little-oh；試求 $\lim_{n\to \infty} z_n =?$

Solution:
我們要計算
\[\mathop {\lim }\limits_{n \to \infty } {z_n} = \mathop {\lim }\limits_{n \to \infty } \left( {t + o\left( {\frac{t}{n}} \right)n} \right)\]
現在考慮任意 sequence $a_n \in o(t/n)$， 則由 little-oh 定義可知
\[\mathop {\lim }\limits_{n \to \infty } \frac{{{a_n}}}{{\frac{t}{n}}} = 0 \Rightarrow \mathop {\lim }\limits_{n \to \infty } \frac{{n{a_n}}}{t} = 0 \]
故現在令 $z_n:= t + n a_n$ 則
\[\mathop {\lim }\limits_{n \to \infty } {z_n} = \mathop {\lim }\limits_{n \to \infty } \left( {t + n{a_n}} \right) = \mathop {\lim }\limits_{n \to \infty } t\left( {1 + \frac{{n{a_n}}}{t}} \right) = t\left( {1 + \mathop {\lim }\limits_{n \to \infty } \frac{{n{a_n}}}{t}} \right) = t\]