What does $n_0$ mean when describing Big-O notation?

2.8k Views Asked by At

When defining the "Big-Oh" notation, we say that $f(n) \text{ is } O(g(n))$ if there is a real constant $c > 0$ and an integer constant $n_0 \geq 1$ such that

$$f(n) \leq c \cdot g(n), \text{ for } n \geq n_0$$

For this definition, what is the meaning of $n_0$?

2

There are 2 best solutions below

1
On BEST ANSWER

Big-O notation's English definition usually says "for sufficiently large values of $n$". The value $n_0$ is that threshold. Until $n$ reaches the value $n_0$ the equation $f(n) \leq c \cdot g(n)$ need not hold. $n_0$ is the point where the equation starts being true and does so until infinity.

Based on the answer by Vignesh Venkat.

0
On

An example: $\sqrt{4n^2+27n+65}=O(n)$ because for $n\ge5, \sqrt{4n^2+27n+65}\le3n$.

You can identify $n_0$ and $c$.

enter image description here