0
$\begingroup$

In our class the following exercises/examples were given:

Compute/find $n_0$ and c from the formal definition of each Landau symbol to show that:

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

Then in the Solution the following was done:

$n_0=1$ and $c=(\frac{1}{12})^8$.

Show: for each $n>n_0: n^{2/3} \ge c \cdot log^8(n)$.

$n^{2/3}=(n^{\frac 1 {12}})^8$.

Then: $c \cdot log^n=log^8(n^{\frac {1}{12}})$

And because in general: $m\ge log(m)$,that implies $m^8\ge log^8(m)$.

The 2nd example was this:

$2^{100}n \in O(n^2)$

Then in the Solution the following was done:

$n_0=2^{100}$ and $c=1$.

Show for each $n>n_0: 2^{100}*n\le n^2$

It is true that: $n_0^2=2^{100}n_0 $ and for all $n>2^{100}: n^2-2^{100}n>n^2 -n \cdot n=n^2 - n^2=0$.

The thing I am the most interested in these two examples is not the solution as much as it is how exactly we evaluate $n_0$ and $c$. I have the following question:

  1. We are looking for $n_0$ and c, but somehow we give values to them? And why those values in particular? Why can't n_0=2? and c=34 (for the first example, or even the second)? Is there a logic behind all of this? In the class it wasn't explained, as two why we take the values that we take. I'd like to have a fundamental understanding of the problem, so that then I can be able to find a case by case solution.

I just want to mention also, that I am fully aware of the big-O and big-$\Omega$ notation (small-o and small-$\omega$ and $\theta$ as well).

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

If you want to show that $f(n) \in \Omega(g(n))$ then you are free to choose $n_0$ and $c$ as long as $\forall n \ge n_0$, $f(n) \ge c \cdot g(n)$ (Reverse the inequality for big-oh.) There is no particular reason to chose one set of values over another, except that you can sometimes make the math easier if you choose wisely.

That said, $n_0 = 2$ and $c=34$ doesn't work in the first example since, for $n=2$:* $$ n^{2/3} = 2^{2/3} < 34 \cdot 1^{8} = 34 \cdot (\log 2)^8 = c \log^8 n. $$

It also doesn't work in the second example since, for $n=2$:* $$ 2^{100} \cdot n = 2^{100} \cdot 2 = 2^{101} > 136 = 34 \cdot 2^2 = c \cdot n^2. $$

* This still doesn't work if you require $n > n_0$ since you can choose, e.g., $n=3$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ " This still doesn't work if you require n>n0 since you can choose, e.g., n=3." I don't understand this line. What are you trying to say? $\endgroup$
    – imbAF
    Jul 30, 2022 at 12:30
  • $\begingroup$ Could you give me another set of values for the first example, and how do you came with those values ? $\endgroup$
    – imbAF
    Jul 30, 2022 at 12:33
  • $\begingroup$ @imbAF, it seems that in your definition of $\Omega(\cdot)$ you are using the "greater than" sign instead of the "greater than or equal to" sign. I'm just point out that, for these specific values, it doesn't make a difference which definition you use: neither works. $\endgroup$
    – Steven
    Jul 30, 2022 at 12:46
  • $\begingroup$ $n^{2/3} \ge c \log^8 n \iff n \ge c^{3/2} \log^{12} n$. We know that $n$ grows asymptotically faster than any polylogarithm so we can pick any $c$ and focus on finding $n_0$. Choosing $c=1$ we have $n \ge \log^{12} n$. The derivative of $n - \log^{12} n$ is positive as soon as $n>1$, so we know that if $n_0 \ge \log^{12} n_0$ for some $n_0 > 1$ then $n \ge \log^{12} n$ for all $n\ge n_0$. We just need to find one such $n_0$. Let's try with a big value, e.g., $n_0 =2^{100}$. We have $2^{100}>(10^3)^{10} =100^{15} > 100^{12} = \log^{12} 2^{100}$, so we are done (here I used $2^{10} > 10^3$). $\endgroup$
    – Steven
    Jul 30, 2022 at 12:59
  • $\begingroup$ I see. One further question. You chose $n_0=2^{100}$. But you could as well choose $n_0=2$ right? Because $2 \ge log^{12} 2$. $\endgroup$
    – imbAF
    Jul 30, 2022 at 13:06

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.