Landau符号：证明或否定

Question

所以问题主义者：

[显示或不证明f，g适用于两个功能：

如果f不在O（g）中，则g在O（f）中

我的反对：

Let f(n) be   f(n) = n^2 : if n is even
                  or n^4 : if n is odd

Let g(n) be   g(n) = n^3

这是f！= O（g）和g！= O（f）的示例。我的例子错了吗？如果是这样，为什么？您还有其他示例吗？

谢谢你！

Answer 1

您的反例工作。一个证明可能看起来像这样：

假设f为O（g）。然后有一个正常数c和一个n0，使得对于n> = n0，f（n）<= c * g（n）。令n'为大于或等于n0的奇数整数。那么我们有n'^ 4 <= c * n'^ 3。将两侧除以n'^ 3得出n'<= c。但是，这对于所有n'> n0都不成立。所以甚至有大于n0的n不能满足条件，这是一个矛盾。]

相反的证明是相似的，除了将两边都除以n'^ 2。

我认为您确定的这种反例是一个很好的例子；一个以渐近递增的方式振荡的函数，以及一个在中间某处出现的函数。