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

Question

如果我设法证明 f(n) = o(g(n))（小 o），那么两个函数之和 f(n) + g(n) 应该被 "bigger" 函数紧紧地束缚似乎很合理g(n).

然而，我很难证明这一点。

Answer 1

以下推理显示了渐近恒等式 (Theta) 意义上的 'tight bound'：

    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

Answer 2

 f(n) = o(g(n)) means that |f(n)|<|C*g(n)|
+
 g(n) = Θ(g(n)) means that |C1*g(n)|<=|g(n)|<=|C2*g(n)|
-------------------------------------------------------
 f(n)+g(n) = Θ(g(n))+o(g(n))=Θ(g(n)) because |C1*g(n)|<=|g(n)+f(n)|<|(C+C2)*g(n)|

Answer 3

这很容易。

如果 f(n) = o(g(n))，那么严格来说我们有 k 当 n > k 时 |f(n)| < 0.5 * |g(n)|（根据 little-O 的定义）。

因此 0.5 * |g(n)| < |f(n) + g(n)| < 1.5 * |g(n)| = Θ(g(n)) 为 n > k。

QED.

如果f(n)和g(n)都是正定的，那么就不需要强small-o条件。但是，如果不是，则需要强条件，否则 f(n) 可能会完全取消 g(n)。（例如 f(n) = -g(n)）

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

if f(n) = o(g(n)), does g(n) + f(n)=Θ(g(n))?

algorithm

theory