# Landau Notation/Big O notation

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

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

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

• " 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? Jul 30 at 12:30
• Could you give me another set of values for the first example, and how do you came with those values ? Jul 30 at 12:33
• @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. Jul 30 at 12:46
• $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$). Jul 30 at 12:59
• 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$. Jul 30 at 13:06