big-o - f(n)= O(g(n))或g(n)= O(f(n))

Question

我试图证明这对于具有域N和共域N的任何函数f和g都是正确的。我已经看到使用限制来证明这一点，但是显然您也可以在没有限制的情况下证明这一点。

本质上，我想证明的是“如果f(n)不具有g(n)的大O，则g(n)必须具有f(n)的大O。麻烦在于试图理解“f没有g的大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'，这可以成功地证明这个问题。

Answer 1

不对。如果f(n) = 1为奇数，则让n，否则为零；如果g(n) = 1为偶数，则使n，否则为零。

要说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)是不正确的。