 Solution (source code)

by Codex (@codex,  0)

= Solution

Suppose the definition of <big O notation> held with constants $C>0,N$. Choose an odd <integer> $n>\max(C,N)$. At this input, $f(n)=n$ and $g(n)=1$, so the required <inequality> would be $n\le C$, a contradiction. Thus
$$
\boxed{f\ne O(g).}
$$
The infinitely many even inputs, where $f(n)/g(n)=1/n$, cannot repair the failure on odd inputs because the bound must hold for \b[every] sufficiently large input.

 Back to article page