Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic definition of Θ- notation, prove that max(f(n), g(n)) = Θ(f(n) + g(n)).
我们需要证明 c1(f(n) + g(n)) <= max(f(n), g(n)) <= c2(f(n) + g(n)) <br > 因为f和g都是非负函数，只需要令c1 = 0.5, c2 = 1即可.
Show that for any real constants a and b, where b > 0,
当n很大时,第一项起主导作用.
Explain why the statement, "The running time of algorithm A is at least O(n^2)," is meaningless.
O-notation确定的是一个上界，而at least确定的是一个下界
Is Is
(1)成立,因为当c0=2时，对所有的n>=1有0<=2^(n+1)<=2*2^n。
(2)不成立，假设存在常数c使得2^(2n)<=c2^n，则有2*n<=lg c+n，即n<=lg c，并不存在一个常数c使得这个不等式对n成立。
Prove Theorem 3.1. For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).
充分性：f(n)=Θ(g(n))意味着存在c1、c2和n0（其中n>=n0）使得0<=c1g(n)<=f(n)<=c2g(n)。我们由此可推出以下两个结论：
- 存在c1和n0（其中n>=n0）使得0<=c1g(n)<=f(n)，即f(n)=Ω(g(n))
- 存在c2和n0（其中n>=n0）使得0<=f(n)<=c2g(n)，即f(n)=O(g(n))
必要性：f(n)=Ω(g(n))意味着“存在c1'和n1（其中n>=n1）使得0<=c1'g(n)<=f(n)”。类似的，f(n)=O(g(n))意味着“存在c2'和n2（其中n>=n2）使得0<=f(n)<=c2'g(n)”。 令c1=c1'，c2=c2'，n0=max{n1, n2}，由Θ的定义我们有：f(n) = Θ(g(n))。
Prove that the running time of an algorithm is Θ(g(n)) if and only if its worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)).
Theorem 3.1.
Prove that o(g(n)) ∩ ω(g(n)) is the empty set.
假设o(g(n)) ∩ ω(g(n))不是一个空集，则等价于说：对于所有的c1,c2>0有0<=c1g(n)<f(n)<c2g(n)其中n>=max(n1, n2)。
我们令c1=c2，可以得出悖论，因此假设不成立，所以o(g(n)) ∩ ω(g(n))是一个空集。
We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n, m), we denote by O(g(n, m)) the set of functions
O(g(n, m)) = {f(n, m): there exist positive constants c, n0, and m0 such that 0 ≤ f(n, m) ≤ cg(n, m)for all n≥n0 and m≥m0}.
Give corresponding definitions for Ω(g(n, m)) and Θ(g(n, m)).
Ω(g(n,m)={f(n,m):there exist positive constants c,n0, and m0 such that 0 ≤ cg(n,m) ≤ f(n,m) for all n≥n0 and m≥m0.
Θ(g(n,m)={f(n,m):there exist positive constants c1,c2,n0, and m0 such that 0 ≤ c1g(n,m) ≤ f(n,m) ≤ c2g(n,m) for all n≥n0 and m≥m0.
Follow @louis1992 on github to help finish this task.