0

I want to prove that $f(n) \neq O(g(n))$ when $f(n) = n$, $g(n) =1$ precisely.

I can prove correct big-Oh expression such as $n = O(n)$, $\lg(n) = O(n)$ etc. but I can't prove incorrect big-Oh expression like above.

How can i prove such thing?

p.s. I don't want to use small-Oh notation for this proof.

Giovanni Mascellani
  • 742
Won Seok Lee
  • 49
  • 1

2 Answers2

1

By definition $f(n) = O(g(n))$ if there exist $k$ and $N$ such that $f(n) \leq k \cdot g(n)$ for $n>N$.

So assume that there exist some $k'$ and $N'$ such that $f(n) \leq k'\cdot g(n)$ for all $n > N'$ and try to derive a contradiction.

Ruben
  • 41
0

$f(n) = O(g(n)), n \to \infty \iff \exists M > 0, n_0 \in \mathbb N : |f(n)| < M|g(n)|, \forall n > n_0$
If $n = O(1)$, then $\exists M > 0, n_0 \in \mathbb N : |n| < M, \forall n > n_0$, but that's a contradiction, as sequence $f(n) = n$ can't be limited by any finite value, so $\forall M > 0, \forall n_0 \in \mathbb N, \exists n^* : |n^*| \geq M$.

Andrei Rykhalski
  • 1,325
  • 9
  • 14