3-3 根据渐进增长率排序
等价类
b) n*sinn
3-4 渐进记号的性质
设f(n )和g(n)为渐进正函数。证明或否定以下的假设：
a) f(n) = O(g(n))蕴含g(n)=O(f(n))
b) f(n)+g(n)=Ф(min(f(n), g(n)))
c) f(n)=O(g(n))蕴含lg(f(n)) = O(lg(g(n)))，其中lg(g(n))>=1且f(n)>=1对足够大的n成立
d) f(n)=O(g(n))蕴含2^(f(n)) = O(2^g(n))
e) f(n)=O(f(n)^2)
f) f(n) = O(g(n))蕴含g(n) = Ω(f(n))
g) f(n) =Ф(f(n/2))
h) f(n) + o(f(n)) = Ф(f(n))
证：a)f(n) = O(g(n)),即存在某个正常数c,n0>0,当n>=n0,有
0<= cg(n) <= f(n),
此时若也存在某个正常数c',n0'>0, 当n>=n0',有
0 <= c'f(n) <= g(n)，若该不等式也满足，则
有n>=max(n0,n0')，
cg(n) <= f(n) <= (1/c')g(n),显然只有
f(n) = Ф(g(n))才成立，则可知题意不符。
b)f(n)+g(n)=Ф(min(f(n), g(n)))，设f(n) =Ф(min(f(n), g(n)))，即f(n) <= g(n), 则存在正常数c1,c2,n0>0,当n>=n0,有
c1*f(n) <= f(n) + g(n) <= c2*f(n)，转化，有
(c1-1)*f(n) <= g(n) <= (c2 -1)*f(n)，要使该式成立，则需要
0 <c1<= 2, 0 < g(n) <= (c2-1)f(n)。已经假设f(n) <= g(n)， f(n)、g(n)为渐进正函数, 则无论c2为何值，n>=n0, 总有g(n) >= (c2-1)f(n)。
此时矛盾，故不成立。
c) f(n)=O(g(n))蕴含lg(f(n)) = O(lg(g(n)))，其中lg(g(n))>=1且f(n)>=1对足够大的n成立
证： lg(f(n))、lg(g(n))不会改变函数的递增特性，因此成立。
d) f(n)=O(g(n))蕴含2^(f(n)) = O(2^g(n))
证：同c)
e) f(n)=O(f(n)^2)
证：假设存在正常数c, n0>0,当n>n0,有
0 <= f(n) <= cf(n)^2, f(n)为渐进正函数，则显然有1 <= c f(n), 故题意成立。
f) f(n) = O(g(n))蕴含g(n) = Ω(f(n))
证：假设存在正常数c, n0>0,当n>n0,有
0 <= f(n) <= cg(n),转化，有
0 <= (1/c)f(n) <= g(n),显然题意成立，有g(n) = Ω(f(n))。
g) f(n) = Ф(f(n/2))
证：假设存在正常数c1，c2, n0>0,当n>n0,有
c1*f(n/2) <= f(n) <= c2*f(n/2),
由于n > n/2, 有f(n) > f(n/2)，则0 <c1<=1,有
c1*f(n/2) <= f(n)
c2 >= f(n)/f(n/2)，若n->正无穷，则存在渐进函数f(n)= a^x, f(n)->正无穷。因此不符合题意。
h) f(n) + o(f(n)) = Ф(f(n))
证：假设存在正常数c1，c2, n0>0,当n>n0,有
c1*f(n) <= f(n)+o(f(n)) <= c2*f(n),转化，有
(c1-1)*f(n) <= o(f(n)) <= (c2-1)*f(n)
已知有任意正常数c, n1>0,当n>n1，有
0 <=o (f(n)) <= c*f(n)
由于c是任意正常数，显然与上述描述矛盾。因此不成立。