algorithm - Big-Theta表記の証明

Question

こんにちは、big-theta を理解するために最善を尽くしました。今では、Big-Oh と Big-Omega の証明の主な概念を理解していますが、演習に近い例を見つけることができませんでした。その証拠：

証人を示すことによって、4n^2 + 4n = Big-Theta(2n^2 + 32n) であることを証明します。

Big-Theta を証明するには、Big-Oh と Big-Omega について証明する必要があることはわかっていますが、どのように始めればよいかわかりません。つまり、右辺の方程式は私を混乱させます。

Answer 1

big-thetaの定義により、2 つの定数 k1 と k2 が存在することを示す必要があります。n のすべての十分に大きな値に対して、

k1 * |2n^2 + 32n| <= |4n^2 + 4n| <= k2 * |2n^2 + 32n|

(関数は正の n に対してすべて正であるため、絶対値を削除できます。) 各不等式を個別に満たすことができることを示すだけで完了です。