渐近符号理解

Question

我正在努力理解这些方程式。我必须确定哪个是错误的，但我真的很想了解该怎么做。

1. $\theta(n)+O(n)=\omega(n)$
2. $O(n)+\sigma(n)=\theta(n)$
3. $\theta(n)+O(n)=O(n)$
4. $f(n)=O(n)$ implies $g(n)=\omega(f(n))$

我知道你必须阅读

$$\theta(n)+O(n)=\Omega(n)$$ 如下：如果在我的主要我有2种方法

main(){
m1();
m2();
}

而方法m1的运行时间为\tetha(n)而m2的运行时间为O(n), 我可以说 main 的 运行 时间是 \Omega(n)?

我认为第三个是错误的..对吗？

Answer 1

你是对的，因为即使 m2 小于 O(n)，m1 的渐近 运行 时间仍然有下界，因为紧界.

编辑： #1 是背后的原因