math - この大きな o 表記のステートメントをどのように証明できますか?

Question

これを証明する方法：

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

私はこの声明を証明できませんでした。

Answer 1

big-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, ∞)ください。任意の を仮定し、任意の に対してwithがあるc > 0ことを証明します。xy > x|f(y)/g(y)| > c

それは十分なヒントを与えるはずです。

そうでない場合: x³ > cfor x ≥ c+1.