在比较的时候有三个方法：
- 利用以上的order
- 对于不好比较的exp，可以同时log，然后比较。
- 目光主要汇聚在最高次的那一项，其他的全都忽略
Transitivity：
holds for O-notation
as f (n) = O(g(n)) and g(n) = O(h(n)) ⇒ f (n) = O(h(n)), where the symbol ⇒ means “implies”.
It also holds for Ω, Θ, o, and ω.
Reflexivity:
- Holds for O,Ω, and Θ,e.g. f(n)=O(f(n)), 4n^2 = Ω(4n^2) , nlogn = Θ(nlogn).
- Not true for o() and ω(), e.g. logn ̸= o(logn), n ̸= ω(n).
Symmetry:
- f (n) = Θ(g(n)) iff g(n) = Θ( f (n)).
- But this is not true for O and Ω, e.g. loglogn = O(logn) but log n ̸= O(log log n).
Monotonicity:
A function f (n) is monotonically increasing if m < n implies f(m) ≤ f(n) and it is strictly increasing if m < n implies f(m) < f(n).
Similarly, f (n) is monotonically decreasing if m < n implies f (m) ≥ f (n) and strictly decreasing if m < n implies f (m) > f (n).
E.g., the running time of merge sorting: cn log n with c > 0 being a constant.
Polynomials:
Given a nonnegative integer d, a polynomial in n is a function of the form p(n) = ∑cini, where ci is a constant for each i, called a coefficient of the polynomial. The degree of a polynomial is the highest power that occurs. E.g. p(n) = 3n^7 − 4n^5 + 1.1n^2 − 100 is a polynomial of degree 7, where c0 =−1, c1 =0, c2 =1.1, c3 =c4 =0, c5 =−4, c6 =0, and c7 =3.
Iterated logarithm
In general: log(k+1) n = log log(k) n.
Iterated logarithm function: log∗ n = min{i ≥ 0 | log(i) n ≤ 1}.
Comparison of growth rates ：
We will use (without proof) that exponential functions grow faster than powers.
We do not prove that logarithmic functions grow slower than powers.
Also, we will prove results like nlogn = o(n^3) using the fact that logarithms grow
slower than powers.
Working with asymptotic notations
To simplify a function by using asymptotic notation: Take the fastest growing additive term and ignore its constant coefficient. This gives Θ(something), which implies both O() and Ω().
3n^2 +5n+2 = Θ(n^2),
Further properties
