在《算法导论》的第四章中用主方法求解递归式，没有说清渐近大于（小于）和多项式大于（小于）的概念，尤其是针对case 3举的例子令我困惑，在查阅了多种解释后，经验证并整理如下。

渐近大于（asymptotically larger）

$f(n)$ 渐近大于 $g(n)$，记作 $f(n) = \omega(g(n))$：
$$
\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = \infty
$$
注意都是非渐近紧缺的界。

多项式大于（polynomially larger）

f(n) is polynomially bigger than g(n) when f(n) asymptotically dominates g(n) even after we multiply g(n) by a very small order polynomial (e.g., $n^{0.00001}$).
参考

$f(n)$ 多项式大于 $g(n)$：
$$
存在常数 \epsilon>0，使得 f(n)= \Omega(g(n)n^\epsilon)，即\lim_{n \rightarrow \infty}\frac{f(n)}{g(n)n^\epsilon} = \infty
$$

例如

1. $n\log_2n$ 只渐近大于 n，因为虽然 $ \lim_{n \rightarrow \infty} \frac{n\log_2n}{n} = \infty$，但对任意常数 $\epsilon>0$，$\lim_{n \rightarrow \infty} \frac{n\log_2n}{n^{1+\epsilon}} = 0$。

2. $2n$ 非渐近大于 $n$，因为 $\lim_{n \rightarrow \infty} \frac{2n}{n} = 2$，即实际上$2n=O(n)$，$n$是渐近紧确的界。

3. $n\log_2n$ 多项式大于 $n^{\log_4 3}$，因为存在常数$\epsilon=0.2$，$\log_4 3+\epsilon = 0.99$，则$\lim_{n \rightarrow \infty} \frac{n\log_2n}{n^{\log_4 3+\epsilon}} = \infty$。

4. $n^2$ 多项式大于 $n\log_2 n$，因为存在常数$\epsilon=0.9$，则$\lim_{n \rightarrow \infty} \frac{n^2}{n^{1+\epsilon} \log_2 n} = \infty$。

---

同理

渐近小于（asymptotically smaller）

$f(n)$ 渐近小于 $g(n)$，也记作 $f(n) = o(g(n))$：
$$
\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = 0
$$

多项式小于（polynomially smaller）

$f(n)$ 多项式小于 $g(n)$
$$存在常数 \epsilon>0，使得 f(n) = O(g(n)n^ \epsilon)，即\lim_{n \rightarrow \infty}\frac{f(n)}{g(n)n^ \epsilon} = 0
$$