find $c$ and n0 in big $O$ notation problem

Question

So i know the definition of big $O$ notation.
But I can't find $n_0$ and $c$ (if $c$ and $n_0$ is given to me then i understand why this is true).
For example if i had:
$3n^2+5=O(n^2)$
$n_0=3$ and $c=4$
But how to find $c$ and $n_0$ only from $3n^2+5=O(n^2)$ ?
Thank you very very much

Answer 1

The first thing to note is that if you have one $c,n_0$ pair that works, you can increase $c$ or $n_0$ or both and it still works. You just have to find one and justify it. In the case of your example, with $f(n)=3n^2+5$ you need $c \gt 3$ or $f(n)$ will get too big. Once you have $c \gt 3$ you just need $n_0$ large enough that the difference between $c$ and $3$ is enough to cover the $+5$ because $cn^2$ will be increasing faster than $3n^2+5$. If you take $c=4$ you have an extra amount of $n^2$, which needs to be greater than $5$, so $n_0=3$ is enough. I could equally well take $c=100, n_0=1000$ and it would work as well.

Answer 2

So, I'm not sure I understand your notation, but I think what you want is a $n_0$ and $c$ such that $3n^2+5\leq cn^2$ for all $n\geq n_0$?

If so, then there isn't always a clear strategy to find $n_0$ and $c$. They will depend on the functions, and even then won't be unique, since big O notation gives qualitative estimates. But a sort of "approach'' to find $n_0$ and $c$ is as follows. If $f(n)=O(g(n))$, consider $$\frac{|f(n)|}{|g(n)|}$$ for large $n$. Any upper bound for this can be your $c$. $n_0$ is a bit trickier. In your case you would get

$$3+\frac{5}{n^2}$$

which is bounded above by $c=4$ for any $n$ such that $5\leq n^2$, i.e. $n\geq 3$. We could also take $c=10$, and $n_0=1$, or $c=3.2$ and $n_0=200$.