私は式
を証明または反証すべきであるN^2 - 4N =ビッグシータ（2^n）は私の知る限りでは証明のn^2 - 4N =ビッグシータ（2^n）の
n^2 - 4n = c * 2^n // use log
2log(n) - log(4n) = log(c) * n * log(2)
2log(n) - (log(4) + log(n)) = log(c) * n //log(2) at base 2 is 1
O（グラム）=私はFを解決するために始めた
f = O(g)
g = O(f)
しかし、どのように私はここから続けるん：私は、次の2つの式を証明する必要がありますか？
big-Oとthetaの表記には違いがあります。あなたの質問では、あなたは両方を使いました。
シータ記号を使用して検査すると、n^2！= 2^nであることがわかります。したがって、falseです。
検査でbig-O表記を使用すると、n^2 < 2^nということが分かります。
あなたの正式な証明としては、log（a - b）をlog（a） - log（b）に拡張することはできません。
n^2-4n=Theta(2^n)が真でないため、証明できません。
big-theta表記法を定義するいくつかの同等の方法があります。 1つは、大きなオメガと大きいオメガの表記であり、すなわち、f=O(g)とf=Omega(g)の場合は、f=Theta(g)となります。これは、nが十分に大きい場合にC*g(n) <= f(n) <= D*g(n)となるような定数C,D>0があることを意味します。つまり、とD*gの間に関数fを「サンドイッチ」することができます。これが当てはまる場合、f(n)/g(n)の制限は、nが無限になるようにする必要があります。そうでなければ、関数の一方が他方より漸近的に速くなり、そのような方法で関数を挟む方法はありません最終的にエスケープします（他の関数の定数倍より速く成長します）。
n^2-4nがTheta(2^n)ではないことを確認するには、それはこのように、以下の制限を見ていればよい：
lim_{n -> infty} (n^2-4n)/2^n = 0
これは、関数2^nが漸近的に速いn^2-4nより成長することを意味し、そうC*2^n挟むn^2-4nに方法はありませんすべてnの場合はC,D>0の場合はD*2^nです。
n> = 0のときにnを見て、n^2と2^nの間に交差がなく、2^nが常にn^2より大きいと仮定すると、O（2^n）は適切ですn^2の上限。 Thetaについては、 – ljeabmreosn
1）aとbを定数とする。 2）0 <= a * 2^n <= n^2-4n <= b * 2^n。 3）0 <= a <=（n^2-4n）/（2^n）≦b。それはあなたを始めるはずです。 – ljeabmreosn