问证明g(n)是o( f(n) )，则f(N)+ g(n)是Theta(f(n))

EN

到目前一切尚好。

接下来，回顾一下，在最好的情况下，0 <= g(n)；这将使您在g(n) + f(n)上有一个下限。

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

假设f( n )对于足够大的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))的意思)。

在我们开始之前，让我们首先说明小o和大Theta符号是什么意思：

小o表示法 形式上，g(n) = o(f(n)) (或g(n) ∈ o(f(n)))持有足够大的n，这意味着对于每一个正常数ε，都存在一个常数N，使得 N>N (+)所有n>N(+)

来自notation。

大Θ表示法 h(n) = Θ(f(n))表示存在正常数k_1、k_2和N，因此对于n > N，k_1 · |f(n)|和k_2 · |f(n)|分别是|h(n)|上的上界和下界。 所有n>N( k_1 )n>N (++)的k_2·x(N)_f(N)_x(N)_(N)_(N)(N)(N)_(N)_(N)

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

Given: 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)|    (*)

去掉(*)中最左边的不等式，除以2，我们有：

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

我们看到，这就是用(++)表示的用常量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))。