两道关于函数的增长的证明题1.证明：f(n)=n^100,对g(n)=2^n是O(g)的,但g不是O(f)的.2.证明：对于f(n)=lg(n^3)和g(n)=log5(6n),f于g有相同的阶

Question

两道关于函数的增长的证明题
1.证明：f(n)=n^100,对g(n)=2^n是O(g)的,但g不是O(f)的.
2.证明：对于f(n)=lg(n^3)和g(n)=log5(6n),f于g有相同的阶

Answer 1

1.只要证明f(n)/g(n)趋于零,当n趋于无穷的时候.使用离散的罗比达法则,有
lim（ f(n)/g(n))
=lim((100*n^99)/(2^n*ln2))
=.
=lim((100!)/(2^n*(ln2)^100))
=0(n趋于无穷时),
反过来,显然g不是0（f）的
2.同1的思路,只证lim（ f(n)/g(n))
=lim【lg(n^3)/（lg(6n)/lg5）】,
=lim【lg5*（lg(n^3)/lg（6n））】,
=lg5*lim【lg(n^3)/lg（6n）】
=lg5*lim【（3/x）/（1/x）】
=lg5*3(n趋于无穷时),
则f和g同阶