# Finding the constants in Landau notation

I am trying to find the constants $$n_0$$ and $$c$$ to show that some given functions belong to the $$O(\cdot)$$ equivalence class. But, while it seems easy, I am not sure whether I am allowed to do what I will showcase below, or rather, what decides which constants I should take into consideration. For example:

$$n^{\frac 2 3} \in \Omega(\log^8n).$$

The definition is: $$g(n) \in \Omega(f(n))$$ if there exist $$c,n_0$$ such that for all $$n > n_0$$, we have $$cf(n) \leq g(n)$$.

So, if I am asked to find the constants $$n_0$$ and $$c$$, with nothing more asked (no extra conditions etc), how can I decide which values to consider?

• "allowed to do what I will showcase below": er, I guess that you forgot to showcase...
– user16034
Commented May 25, 2022 at 6:54

The assertion can be proved without finding a particular value of $$n_0$$, but by just proving there exists an $$n_0$$ satisfying the desired conditions. More specifically, to show $$n^{2/3}$$ grows asymptotically faster than $$(\log n)^8$$, it suffices to show that $$\lim_{n \rightarrow \infty} \frac{n^{2/3}}{(\log n)^8} \ =\infty$$, which can be shown by repeated application of L'Hospital's rule.
Suppose that $$\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = \infty$$. By definition, this means the ratio $$\frac{f(n)}{g(n)}$$ grows without bound, i.e. for all $$B > 0$$, $$\frac{f(n)}{g(n)} \ge B$$ for all sufficiently large $$n$$. In other words, for all $$B > 0$$, there exists $$n_0 > 0$$ such that $$\frac{f(n)}{g(n)} \ge B$$ for all $$n \ge n_0$$. In particular, taking $$B=1$$, we get that there exists $$n_0$$ such that $$f(n) \ge g(n)$$ for all $$n \ge n_0$$. This implies $$f(n) = \Omega(g(n))$$.
By solving for $$n_0$$ and $$c$$ the system of inequations
$$\begin{cases}n>n_0,\\f(n)>c\,g(n).\end{cases}$$
Concretely, you can study the function $$\dfrac{f(n)}{g(n)}$$ and find a lower bound (f.i. the global minimum, or any gross approximation).