math - 函数 f 不在 O(g) 中，g 不在 O(f) 中

Question

问题是:

Show or disprove that for two functions f,g, if f is not in O(g) then g is in 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 都成立；所以甚至有 n 个大于 n0 的条件不成立，这是一个矛盾。

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

我认为你指出的那种反例是一个很好的例子；一个以渐近递增量振荡的函数和一个位于中间某处的函数。