我正在研究f(n) + o(f(n)) = theta (f(n))的证据，我在证明我无法理解的证据中遇到了一个部分。
我们让f(n)和g(n)渐近正函数并假设g(n) = O(f(n))。在证明中，它表明，既然我们知道所有f(n) + g(n) ≥ f(n)的n，我们可以得出结论f(n) + g(n) = Omega((f(n))。我们也可以类似地得出结论f(n) + g(n) ≤ 2 f(n)。因此f(n) + g(n) = O(f(n))。我无法理解为什么f(n) + g(n) = Omega((f(n))和f(n) + g(n) = O(f(n))会是真的。当我们将g(n)添加到f(n)时，我们如何能够证明紧密下限是特别的？我们从g(n)的价值中得出的结论是什么？
证明f(n)是theta(g(n))的一种方法是证明两个单独的陈述：f(n)是omega(g(n))，而f(n)是O(g(n))。很明显，从这些符号的定义来看，这种证明方式是正确的。
在这个确切的问题中，如果我们选择一些常数c等于1，我们将为每个n，f(n) + g(n) >= c * f(n)，因此，根据定义，显示f(n) + g(n)是Omega(f(n))。此外，对于O(f(n))部分，如果我们在这种情况下选择常数c为2，我们需要证明存在一些n0，使得每个f(n) + g(n) <= c * f(n)的n > n0，相当于每个g(n) <= f(n)的n > n0，这相当于问题陈述中给出的g(n) = O(f(n))的定义。
希望这可以帮助。