関数が負の値を持つときのBig-O表記

Question

2n^2 - 2n -7 = O（n^2）、nが1または2のとき、f（n）の負の値を持つことを証明する必要があります。私はBig-Oが正しいことを証明する方法はわかりません。あなたの助けと助言は高く評価されます。

   f(n) = 2n^2 - 2n -7 = O(n^2) if c=2; 
       n=1->2(1)^2 - 2(1) -7 = -7 <= 2*(1)^2 
       n=2->2(2)^2 - 2(2) -7 = -3 <= 2*(2)^2 
       n=3->2(3)^2 - 2(3) -7 = 14 <= 2*(3)^2 

Answer 1

Big-Ohの定義は、ローカル動作よりも漸近的な動作に関係します。関数が負の値になってnという値になった場合、それが振動していると言えば、それ以上の心配があるかもしれません。しかし、この関数では問題はありません。あなただけが選択できるいくつかの値よりも大きいすべての値に対して関数を考慮することは自由です。n0したがって、関数が負の値になると早期に負になる場合は、それらの数値が使用されないように証明を書いてください。例えば：

ベースケース：n = 3の場合、f(n) = 2*3*3 - 2*3 - 7 = 18 - 6 - 7 = 5 <= 9 * c = c * 3 * 3 = c * n^2の場合。これは、c >= 5/9であれば真です。

誘導仮説：すべてのnが3から始まり、kになると仮定すると、f(n) <= c * n^2と仮定します。

誘導ステップ：f(k+1) <= c * (k+1)^2を示す必要があります。我々はf(k+1) = 2(k+1)^2 - 2(k+1) - 7 = 2k^2+4k+2 - 2k - 2 - 7 = 2k^2 + 2k - 7 < 2k^2 + 4k < 2k^2 + 4k + 2 = 2(k^2 + 2k + 1) = 2(k+1)^2を持っているので、選択はc = 2がここで働く。

事実上、nが増加すると、2n^2 - 2n - 7は常に2n^2より小さくなることが明らかです。