algorithm - 如果 f(n) = o(g(n))，g(n) + f(n)=Θ(g(n)) 吗？

Question

如果我设法证明 f(n) = o(g(n))(小 o)，那么这两个函数的总和 f( n) + g(n) 应该被“更大”的函数 g(n) 紧紧束缚。

然而，我在证明这一点时遇到了一些麻烦。

Answer 1

以下推理显示了渐近恒等式 (Theta) 意义上的“紧界”:

    f = o(g)
<=> lim_n->oo ( f(n)/g(n) ) = 0
 => lim_n->oo ( (f(n)+g(n))/g(n) )
  = lim_n->oo ( f(n)/g(n) ) + lim_n->oo ( g(n)/g(n) )
  =           0             +            1