[解決済み] f(n) = O(g(n)) もしくは g(n) = O(f(n))

質問

ドメインとコドメインがNの関数fとgについて、これが正しいことを証明したい。極限を使って証明するのを見たことがあるが、極限なしでも証明できるらしい。

私が証明しようとしているのは、「f(n) が g(n) の big-O を持たないなら、g(n) は f(n) の big-O を持たなければならない」ということです。私が困っているのは、"f doesn't have a big-O of g"が何を意味するのか理解しようとすることです。

f(n) != O(g(n)) ならば、n のすべての値に対してこの不等式を満たす c は存在しない、ということだと思います。だからといって、g(n) <= c'f(n) を満たすc'が存在することを証明するわけでもなく、それで問題の証明は成功する。

どのように解決するのですか？

そうではありません。Let f(n) = 1 もし n が奇数でそれ以外は0であり g(n) = 1 もし n は偶数で、それ以外は0である。

というのは f は O(g) は一定と言うことでしょう。 C > 0 と N > 0 そのような n > N を意味します。 f(n) <= C g(n) . とします。 n = 2 * N + 1 というように n は奇数である。では f(n) = 1 しかし g(n) = 0 そうすると f(n) <= C * g(n) は不可能です。このように f は O(g) が真でない場合。

同様に、以下のことを示すことができます。 g は O(f) が真でない場合。