これがドメインとコドメイン N を持つ任意の関数 f と g に対して正しいことを証明しようとしています。制限を使用して証明されているのを見てきましたが、制限なしで証明することもできるようです。
基本的に私が証明しようとしているのは、「f(n) に g(n) の big-O がない場合、g(n) には f(n) の big-O が必要です。私が持っているもの問題は、「f には g の Big-O がない」という意味を理解しようとすることです。
big-O の正式な定義によれば、f(n) = O(g(n)) の場合、ある N と定数 c に対して n>=N -> f(n) <= cg(n) となります。f(n) != O(g(n)) の場合、n のすべての値に対してこの不等式を満たす c が存在しないことを意味すると思います。しかし、その事実を使用して g(n) = O(f(n)) を証明するために何ができるかわかりません。これは、g(n) <= c'f(n) に対して c' が存在することを証明するものではありません。