大噢和Omega符號複雜證據

Question

1. 證明是n 不爲O（n ）
2. 證明是n 不在OMEGA（正）

Answer 1

1. 假設N 3是O（N²），則存在一些對正的常數的c和n₀使得n³ ≤ cn²爲全部n ≥ n₀，但對於任何常數c，這是非常虛假的n > c，因此我們有矛盾。

2. 假設N 3是在Ω（N 4），則存在一些對正的常數的c和n₀使得n³ ≥ cn⁴所有n ≥ n₀，但對於任何恆定c，這是平凡假時n > max(1,1/c)，從而我們有一個矛盾。