4
$\begingroup$

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?

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

2 Answers 2

1
$\begingroup$

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))$.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.