Big $\mathcal{O}$ Notation $f(N)=\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$

Question

If $f(N)=\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$ (the big-oh) means that $\frac{1}{\sqrt{N}}$ grows faster than $f(N)$ as $N \to \infty$. So it is possible to take $f(N)=\frac{1}{N}$ or $f(N)=\frac{1}{N^2}$.

Am I correct ?

Answer 1

By definition

$$f(x) = \mathcal{O}(g(x)) \iff f(x) \leq cg(x)$$

In your case let $f(N)=\dfrac{1}{N^a}$ with $a \in \mathbb{N} $ and $\,g(N)=\dfrac{1}{\sqrt{N}}$, then $$\lim_{N\to\infty}\frac{f(N)}{cg(N)} = \frac{\frac{1}{N^a}}{\frac{c}{\sqrt{N}}} = \frac{\sqrt{N}}{cN^a} = \sqrt{\frac{N}{(cN^a)^2}}= \frac{1}{cN^{\frac{a2-1}{2}}} =0 $$ Therefore $$f(N) \leq \dfrac{c}{\sqrt{N}}\implies f(N) = \mathcal{O}\left(g(N)\right) $$ $\tag*{$\Box$}$ So you're right.

Answer 2

When you say $f(N) = \mathcal{O} \left( g(N) \right)$ this means that $f(N)$ is equal to some function that has the property

$$ f(N) \leq c g(N) $$

for all $N \geq N_0$, and $c$ some constant. In your case this means that there's an $N_0$ and constant $c$ for which

$$f(N) \leq \frac{c}{\sqrt{N}}.$$

Therefore your choices are both valid as candidates for $f(N)$, but trivially even $f(N) = 0$ is a suitable candidate.