math - 我怎样才能证明这个大符号的陈述？

Question

如何证明这一点：

x^7 = O(x^10)
x^10 = O(x^7)?

我无法证明这个说法。

Answer 1

让我们看一下大O符号的定义。

f ∈ O(g) <=> (∃ x) (∃ c > 0) (∀ y > x) (|f(y)| <= c⋅|g(y)|)

右手边可以表述为“商f/g有界足够大x”。

因此，为了证明f ∈ O(g)，查看商，选择一个（较大的）x并尝试找到一个界限。对于第一种情况，商是

x⁷ / x¹⁰ = 1/x³

一个界限x ≥ 1是显而易见的。

要反驳f ∈ O(g)，请查看商并证明它在每个区间上假定任意大模值[x, ∞)。假设一个任意的c > 0，并证明对于任意的x，存在一个y > xwith |f(y)/g(y)| > c。

这应该给出足够的提示。

如果不是：x³ > c对于x ≥ c+1.