1
$\begingroup$

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$?

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Can n0 be negative??? $\endgroup$ Commented Sep 19, 2022 at 15:20
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .