big-o - 使用大 o 和小 o 符号的证明

Question

我目前试图证明如果 g 在 o(f) 中，那么 f 不在 O(g) 中。

我已经尝试定义证明 g 是 o(f) 的任意变量，但我完全坚持下一步应该去哪里

Answer 1

如果 f ∊ O(g)，这意味着存在常数 c > 0 和 N，使得对于所有 n ≥ N，f(n) ≤ c * g(n)。

little o的定义是，如果 g ∊ o(f) 那么对于每个常数 ε > 0，都有一些 N'（不一定与上面的 N 相同）使得对于所有 n ≥ N'，绝对值 | g(n)| ≤ ε * f(n)。

我们需要证明，如果第一个不等式为真，那么第二个不等式不成立。首先将第一个不等式重新排列为 g(n) ≥ f(n)/c，然后选择 ε 为 0 到 1/c 之间的某个数字。显然，对于任何n，以下两个不可能都为真，更不用说所有 n ≥ max(N, N')：

• g(n) ≥ f(n)/c
• |g(n)| ≤ ε * f(n) < f(n)/c

这是一个直接的矛盾，因此 f ∊ O(g) 和 g ∊ o(f) 不可能都为真。