algorithm - 如何对渐近符号函数集进行操作，即。 Big-O + Big-Omega？

Question

我正在尝试确定以下陈述是对还是错。

如果 f(n) ∈ O(n) 且 g(n) ∈ Ω(n)，则 f(n) + g(n) ∈ Θ(n)。

我想我理解添加相同的渐近 big-O。 O(n) + O(n) = O(n)但是，我不确定是否要对其他组合进行添加或操作。

例如:如果 f(n) ∈ Θ(n log n)，则 f(n) * n = ?

这个答案可以同时是 O(n^2*logn) 和 Θ(n^2*logn) 吗？

提前致谢!

Answer 1

你可以使用这些符号的定义，并尝试为它们找到一个证明或反例。

如果 f(n) = O(n) 且 g(n) = Omega(n)，则 f(n) + g(n ) 不一定在 Theta(n) 中!作为矛盾，如果 f(n) = n 和 g(n) = n^2，则 f(n) + g(n) = Theta (n^2)。另一方面，如果 f(n) = n 和 g(n) = n，则 f(n) + g(n) = Theta( n)。因此，您可以只说 f(n) + g(n) = Omega(n)，仅此而已。