Asymptotic Notation

描述兩個函數在輸入n夠大的時候的成長速率關係。
多項式係數、log的底數(log的係數也是)不影響成長速率關係。

簡易growth order定義
\( O \)視為\( \geq \)
\( \Theta \)視為\( = \)
\( \Omega \)視為\( \leq \)
\( o \)視為\( > \)
\( \omega \)視為\( < \)
這裡的大於小於等於，代表growth order的關係，
不代表函數之間大小的關係，

Example:
\( f(n)= 3n^2 +2 \)
\( g(n)=n^2 \)

growth order的關係:
\( f(n)=O(g(n)), c_0=4,n_0=2 \)
並不代表 \( g(n)\geq f(n) \)

ex:
\( 3n^4 = O(n^4) \)
\( 3n^4 = O(n^6) \)
\( \log_{3}n=O(\lg n) \)

big-O

\( f(n)=O(g(n)) \)
\( g(n) \) is asymptotically upper bound of \( f(n) \).

\( \exists c_0,n_0>0 \)
\( \rightarrow \forall n\geq n_0 \; (0\leq f(n)\leq c_0g(n)) \)

big-omega

\( f(n)=\Omega(g(n)) \)
\( g(n) \) is asymptotically lower bound of \( f(n) \).

\( \exists c_0,n_0>0 \)
\( \rightarrow \forall n\geq n_0 \; (0\leq c_0g(n)\leq f(n)) \)

big-theta

\( f(n)=\Theta(g(n)) \)
\( g(n) \) is asymptotically tight bound of \( f(n) \).

\( \exists c_0,c_1,n_0>0 \)
\( \rightarrow \forall n\geq n_0 \; (0\leq c_0g(n)\leq f(n)\leq c_1g(n)) \)

small-o

\( f(n)=o(g(n)) \)
\( g(n) \) is asymptotically strict upper bound of \( f(n) \).

\( \forall c_0>0,\exists n_0>0 \)
\( \rightarrow \forall n\geq n_0 \; (0\leq f(n) < c_0g(n)) \)

small-omega

\( f(n)=\omega(g(n)) \)
\( g(n) \) is asymptotically strict lower bound of \( f(n) \).

\( \forall c_0>0,\exists n_0>0 \)
\( \rightarrow \forall n\geq n_0 \; (0 \leq c_0g(n)< f(n)) \)

image reference

set

Asymptotic notation 可以視為是函數的集合:
Example:
\( O(n^2)=\{3n^2-1, n^2, n, \log n,\dots\} \)
\( o(n^3)=\{3n^2-1, n^2, n, \log n,\dots\} \)
\( \Omega(n)=\{3n^2-1, n^2, n,\dots\} \)

這裡用=代表growth order的關係，而不是 \( \in \)。
Example:
\( f(n)=3n^2+1 \)
\( g(n)=n^2 \)
\( f(n)=O(g(n)) \), 而不是 \( f(n)\in O(g(n)) \)

exercise

Give two functions that is in \( O(n^2) \) but not in \( o(n^2) \).
ans.
\( 3n^2, n^2 \)
Give two functions that is in \( \Omega(n^2) \) but not in \( \omega(n^2) \).
ans.
\( 4n^2, 3n^2 \)
True or False.
\( 2^{n+1}=O(2^n) \)
ans.
True. \( 2(2^n)=O(2^n) \)
True or False.
\( 2^{2n}=O(2^n) \)
ans.
False. \( 2^{2n}=(2^2)^n=4^n\neq O(2^n) \)

properties

\( f(n)=O(g(n)) \cap f(n)=\Omega(g(n)) \Leftrightarrow f(n)=\Theta(g(n)) \)

proof

因為\( f(n)=O(g(n)) \)，所以存在\( c_1,n_1>0 \), 使得任意\( n>n_1 \)，\( 0\leq f(n) \leq c_1g(n) \)
因為\( f(n)=\Omega(g(n)) \), 所以存在 \( c_2,n_2>0 \), 使得任意\( n>n_2 \)， \( 0\leq g(n) \leq c_2f(n) \)
取\( c_0=\frac{1}{c_2} \)，得 \( 0\leq c_0g(n)\leq f(n) \)
取\( n_0=max(n_1,n_2) \)，得 \( \exists c_0,c_1,n_0>0\forall n>n_0 \rightarrow 0\leq c_0g(n)\leq f(n)\leq c_1g(n) \)

If \( f(n)=O(r(n)) \; \cap \; g(n)=O(s(n)) \)
\( \rightarrow f(n)+g(n) = O(r(n)+s(n)) \)

proof
Since \( f(n)=O(r(n)) \)
\( \rightarrow \exists c_1,n_1 >0 \) such that \( \forall n\geq n_1 (0\leq f(n)\leq c_1r(n)) \)

Since \( g(n)=O(s(n) \)
\( \rightarrow \exists c_2,n_2>0 \) such that \( \forall n\geq n_1 (0\leq g(n)\leq c_2s(n)) \)
Let \( c_0=c_1\cdot c_2, n_0=max(n_1,n_2) \),

We conclude that
\( 0\leq f(n)+g(n) \leq c_0(s(n)+r(n)) \)
Q.E.D.
If \( f(n)=O(r(n)) \; \cap \; g(n)=O(s(n)) \)
\( \rightarrow f(n)\cdot g(n) = O(r(n)\cdot s(n)) \)

proof
Since \( f(n)=O(r(n)) \)
\( \exists c_1, n_1>0 \) such taht \( \forall n\geq n_1(0\leq f(n)\leq c_1r(n)) \)

Since \( g(n)=O(s(n)) \)
\( \rightarrow \exists c_2, n_2>0 \) such that \( \forall n\geq n_2 (0\leq g(n)\leq c_2s(n)) \)

Let \( c_0=c_1\cdot c_2, n_0=max(n_1,n_2) \)
We conclude that
\( \forall n>n_0 (f(n)\cdot g(n)\leq c_0(r(n)\cdot s(n))) \)
Q.E.D.

\( f(n)=O(g(n)) \rightarrow f(n)+g(n)=O(g(n)) \)