证明如果 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)) 的意思）。

Answer 2

到目前为止一切顺利。

下一步，回想一下，在最好的情况下，0 <= g(n)；这应该让你得到 g(n) + f(n).

的下限

Answer 3

在我们开始之前，让我们首先说明 little-o 和 Big-Theta 符号的含义：

Little-o notation

Formally, that g(n) = o(f(n)) (or g(n) ∈ o(f(n))) holds for sufficiently large n means that for every positive constant ε there exists a constant N such that
|g(n)| ≤ ε*|f(n)|, for all n > N                                 (+)

来自 https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation.

Big-Θ notation

h(n) = Θ(f(n)) means there exists positive constants k_1, k_2 and N, such that k_1 · |f(n)| and k_2 · |f(n)| is an upper bound and lower bound on on |h(n)|, respectively, for n > N, i.e.
k_1 · |f(n)| ≤ |h(n)| ≤ k_2 · |f(n)|, for all n > N              (++)

来自 https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation.

给定： g(n) ∈ o(f(n))

因此，在我们的例子中，对于每个 ε>0，我们可以找到一些常量 N 使得 (+)，对于我们的函数 g(n) 和 f(n) .因此，对于 n>N，我们有

|g(n)| ≤ ε*|f(n)|, for some ε>0, for all n>N

Choose a constant ε < 1 (recall, the above holds for all ε > 0), 
with accompanied constant N. 
Then the following holds for all n>N

    ε(|g(n)| + |f(n)|) ≤ 2|f(n)| ≤ 2(|g(n)| + |f(n)|) ≤ 4*|f(n)|    (*)

去掉 (*) 中的 left-most 不等式除以 2，我们有：

|f(n)| ≤ |g(n)| + |f(n)| ≤ 2*|f(n)|, n>N                            (**)

我们看到这就是定义的 Big-Θ 符号，如 (++) 中所示，具有常量 k_1 = 1、k_2 = 2 和 h(n) = g(n)+f(n)。因此

(**) => g(n) + f(n) is in Θ(f(n))

答案我们已经证明 g(n) ∈ o(f(n)) 意味着 (g(n) + f(n)) ∈ Θ(f(n))。

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

Proving if g(n) is o(f(n)), then f(n) + g(n) is Theta(f(n))

algorithm

math

time-complexity

little-o