- #1
evinda
Gold Member
MHB
- 3,836
- 0
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)
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)
Last edited: