已知big-oh证明small-oh

Question

已知f(n) 是 O(g(n)) 怎么证明 f(n) 是 o(n * g(n)). QAQ

Answer 1

题目可以改写成：
已知：
$\exists\;c, n_0, 使得 T(n)\leq{c\cdot{g(n)}}\;\;\forall{n}\geq{n_0}$ ①
求证：
$\forall{\;c}>0,\;\exists\;n_0, 使得 T(n)\leq{c\cdot{ng(n)}}\;\;\forall{n}\geq{n_0}$ ②

解：
由①可得：
$\exists{\;c},n_0, 使得 T(n)\leq{c\cdot{g(n)}}\leq{c\cdot{ng(n)}}\;\;\forall{n}\geq{n_0}$ ③

$\because\forall\;{c}>0,\;\;c\cdot{g(n)}\leq{c\cdot{ng(n)}}$ ④
(潜在条件n ≥ 1)

综合③④可得②，得证。