1

What I have come to understand is that $f(n)$ is said to be $o(g(n))$ if and only if for every $c>0$, there exists $n_0\in\mathbb{N}$ such that $f(n)<c\times g(n), \forall n\geq n_0$.

Have you got it right?

If yes, what would $f(n)=o(1)$ mean? Does it mean that for sufficiently large $n$, $f(n)$ is $0$? If yes, does it mean $f(n)$ is bounded by $1$ for large large values of $n$?

  • 2
    It simply means that $f(n)$ tends to $0$ when $n$ tends to $\infty$. – Bernard Sep 16 '21 at 11:36
  • 1
    Different authors sometimes use slightly varying definitions (for example, some authors will put absolute values where you put none), but I agree with you. Assuming $f\ge 0$, then $f(n)=o(1)$ means that $\lim_{n\to\infty} f(n)=0$. – Maximilian Janisch Sep 16 '21 at 11:37

1 Answers1

0

(Little-o, $o()):$ Let $f(n)$ and $g(n)$ be functions that map positive integers to positive real numbers. We say that $f(n)$ is $o(g(n))$ (or $f(n) \in o(g(n)))$ if for any real constant $c>0$, there exists an integer constant $n_{0} \geq 1$ such that $f(n)<c * g(n)$ for every integer $n \geq n_{0}$

More here: Link

F. A. Mala
  • 1