algorithm - 证明如果 g(n) 是 o(f(n))，则 f(n) + g(n) 是 Theta(f(n))

Question

所以我正在努力证明(或反驳)上述问题。我觉得这是真的，但我不确定如何展示它。

同样，问题是如果 g(n) 是 o(f(n))，则 f(n) + g(n) 是 Theta(f(n))

请注意，这是一个little-o，不是一个big-o!!!

到目前为止，我已经设法(轻松地)证明:

g(n) = o(f(n)) -> g(n) < c*f(n)

那么 g(n) + f(n) < (c+1)*f(n) -> (g(n) + f(n)) = O(f(n))

但是，为了展示 Big Omega，我不确定该怎么做。

我这样做对吗？

编辑:每个人都提供了很大的帮助，但我只能标记一个。谢谢。

Answer 1

一种选择是取 (f(n) + g(n))/f(n) 的极限，因为 n 趋于无穷大。如果这收敛到一个有限的非零值，则 f(n) + g(n) = Θ(f(n))。

假设对于足够大的 n，f(n) 不为零，则上述比率在极限情况下为

(f(n) + g(n)) / f(n)

= f(n) / f(n) + g(n) / f(n)

= 1 + g(n) / f(n).

因此，取极限为 n 趋于无穷大，上述表达式收敛于 1，因为比率趋于零(这就是 g(n) 为 o(f(n)) 的意思)。