MHB Disprove "f(n)=O(f(n)^2): A Mathematical Analysis

[evinda]

Hello! (Wave)

I want to prove or disapprove the statement $f(n)=O(f(n)^2)$.

That's what I have tried:

The statement is false.
Let $f(n)=\frac{1}{n}, n \in \mathbb{N}$.
We suppose that $f(n)=O(f(n)^2)$. That means that $\exists n_0 \in \mathbb{N}, c>0$ such that $\forall n \geq n_0$:
$$\frac{1}{n}=f(n) \leq c f(n)^2=c \frac{1}{n^2} \Rightarrow \frac{n^2}{n} \leq c \Rightarrow n \geq c. \text{ Contradiction.}$$

We notice that $f(n)=O(f(n)^2)$ iff $\exists c'>0, n_0' \in \mathbb{N} $ such that $\forall n \geq n_0'$: $f(n) \leq c' f(n)^2 \overset{f(n) \neq 0}{ \Rightarrow } 1 \leq c' f(n) \Rightarrow f(n) \geq \frac{1}{c'}:=C \Rightarrow f(n) \in \Omega(1)$.

Is the last paragraph necessary? (Thinking)

 

[MarkFL]

I edited the title of your thread for the following reason:

disprove: prove that (something) is false, refute.

disapprove: have or express an unfavorable opinion about something.