# If $f(n)=O(g(n))$ can I say there exists a $n_0$ for a specific $c$?

I've been working on an asymptotic proof and I want to start with saying that since $$\log z=O(z)$$ then $$\log z\le\frac1 9z$$ for $$z\ge z_0$$. In this example I'm picking $$c=\frac1 9$$ and hoping $$z_0$$ exists, but is $$z_0$$ guaranteed to exist if I pick $$c$$?

## 1 Answer

Let's take as an example $$f(n) = g(n) = n$$ and $$c = 1/2$$. Does there exist an $$n_0$$ such that $$f(n) \leq cg(n)$$ for all $$n \geq n_0$$?

In your case, you know more: $$\log n = o(n)$$. This means that $$\lim_{n\to\infty} \frac{\log n}{n} = 0,$$ which implies that for every $$c$$ there exists $$n_0$$ such that $$\frac{\log n}{n} \leq c$$ for all $$n \geq n_0$$.

• I think this makes sense. Since the limit is approaching zero, for any given $c$ the $n_0$ will be the $n$ where $\frac{\log(n)}{n} = c$? Apr 27, 2021 at 21:22
• You can take this $n_0$ since $\frac{\log n}{n}$ is monotone, but in general you are not guaranteed anything like that. Apr 27, 2021 at 21:35