漸近記法

Question

これはアルゴリズムにMIT OpenCourse はじめの割り当てから漸近記法上の問題であり、次の文のそれぞれについて
、それがあるかどうかを決定常に真、決して真、または時にはtrue漸近的に非負関数fおよびgです。 が常に真の場合またはが真ではないの理由を説明してください。 の場合はtrueの場合は、それが真であるものと偽であるものの1つを与えます。

f(n) ≠ O(g(n)) and g(n) ≠ O(f(n)) (both are Big-O notes) 

私はそれが真決してだと思います。ここに私の証明があります：

f(n) ≠ O(g(n)) 
=> f(n) = w(g(n)) (little-omega note) 
=> g(n) = o(f(n)) (little-o note) 
=> g(n) = O(f(n)) (big-O note) 

結果はg(n) ≠ O(f(n)) (Big-O note)に矛盾します。同様に、

g(n) ≠ O(f(n)) 
=> g(n) = w(f(n)) (little-omega note) 
=> f(n) = o(g(n)) (little-o note) 
=> f(n) = O(g(n)) (big-O note) 

f(n) ≠ O(g(n)) (Big-O note)と矛盾します。

解決策は、時々真であると言います：私は私の証拠に間違って行っている

For f(n) = 1 and g(n) = ||n*sin(n)|| it is true, 
while for any f(n) = O(g(n)), e.g. f(n) = g(n) = 1, it is not true. 

？また、私は解決策を理解できません。 ||n*sin(n)||は私にベクトルノルムのように見えます。

Answer 1

最初は真実ではありません。このf(n) ≠ O(g(n))からは、これに従わない：f(n) = w(g(n))。 2つの関数は、ある点で交差してから場所を叩くかもしれません。もう1つは（単純な単語を使用すると）大きくなります。 （n）> f（n）（例えば、π/ 2）が存在するnsが存在する場合には、この関数は、 。私はn*sin(n)を考える

Answer 2

はちょうどそれもビッグO &のでf(n) ≠ O(g(n)) and g(n) ≠ O(f(n))

Aを定義するために使用定数乗算器のすべての選択肢について、nのその後の値について&より小さいf(n) = 1大きくなっ保つ機能であることを示していますg(n) = 2*sin(n)のようなネイティブに選択された機能はここでうまく行かないでしょう。これもまた、f(n) = 1を交互に置き続けると考えられるかもしれないが、g(n) = O(f(n)) : M*f(n) > g(n) for M = 3など