Coursera 上 Algorithms: Design and Analysis, Part 1 by Tim Roughgarden 的学习笔记。第二课，有关时间复杂度。
The Gist
时间复杂度计算概略地讲，就是“suppress constant factors and lower-order terms”
Big-Oh Notation
Formal Definition: $T(n) = O(f(n))$ \
if and only if exist constants $c, n_0$ such that $T(n) \le cf(n)$ \
for all $n \gt n_0$
即 $n \rightarrow +\infty$ 时，$cf(n)$ 为 $T(n)$ 上限
Omega Notation
Formal Definition: $T(n) = \Omega(f(n))$ \
if and only if exist constants $c, n_0$ such that $T(n) \ge cf(n)$ \
for all $n \gt n_0$
即 $n \rightarrow +\infty$ 时，$cf(n)$ 为 $T(n)$ 下限
Theta Notation
Formal Definition: $T(n) = \Theta(f(n))$ \
if and only if $T(n)=O(f(n))$ and $\Omega(n)=O(f(n))$
即 $n \rightarrow +\infty$ 时，$cf(n)$ 既能作 $T(n)$ 下限也能作上限，