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))
因为f和g都是非负函数，只需要令c1 = 0.5, c2 = 1即可.
English:
Use the definition of Θ-notation and set it up with the given values:
0 <= c1(f(n) + g(n)) <= max(f(n), g(n)) <= c2(f(n) + g(n))
---If we can Solve All inequalities, we can then use that as proof for the definition of Θ-notation.
c2 = 1: This holds because the Max must be lower than the sum of the two functions.
c1 = 1/2: This holds because the Max can at its lowest be equal to 1/2 of the Sum of the two functions.
0 <= c1(f(n) + g(n)) is trivial.
Thus, since all inequalities hold, we've proven that: max(f(n), g(n)) = Θ(f(n) + g(n)).
Show that for any real constants a and b, where b > 0,
Here (n + a) <= 2n, when |a| <= n and (n + a) >= n/2, when |a| <= n/2.
So n >= 2a
So we can write,
0 <= n/2 <= (n + a) <= 2n
Now raising to the power b, we get
0 <= (n/2)b <= (n + a)b <= (2n)b
0 <= (1/2)bnb <= (n + a)b <= 2bnb
Comparing this with 0 <= c1nb <= (n + a)b <= c2nb, we get
c1 = (1/2)b , c2 = 2b and n0 = 2a
Therefore (n + a)b = Θ(nb).
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成立。
English: for f(n) = O(g(n)), the definition of O-notation is: 0 <= f(n) <= c(g(n)) for all n > n0.
(1) 2^(n+1) = 2(2^n) <= c*2^n. If c = 2, the inequality holds and we prove 2^(n+1) = O(2^n) to be True! Answer: Yes.
(2) 2^2n = (2^n)^2. There is no possible constant c that can make 2^n into (2^n)^2. Thus, 2^2n =/= O(2^n). Answer: No.
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.