MHB Proving $\lg^2 n=o(2^{\sqrt{2 \lg n}})$ and $2^{2^{n+1}}=\omega(2^{2^n})$

[evinda]

Yep! (Nod)

According to the definition, it is $f(n)=o(g(n))$, if $\forall c>0, \exists n_0 \geq 0$ such that $\forall n \geq n_0$:
$$0 \leq f(n)<c g(n)$$

So, do I have to say also at the beginning, that $\lg^2 n \geq 0, \forall n \geq 0$ ? (Thinking)

 

[I like Serena]

According to the definition, it is $f(n)=o(g(n))$, if $\forall c>0, \exists n_0 \geq 0$ such that $\forall n \geq n_0$:
$$0 \leq f(n)<c g(n)$$

So, do I have to say also at the beginning, that $\lg^2 n \geq 0, \forall n \geq 0$ ? (Thinking)

Well... that's not true is it? (Wondering)
You'll need a larger lower bound.

 

[evinda]

Well... that's not true is it? (Wondering)
You'll need a larger lower bound.

Is it $\lg^2 n \geq 0, \forall n \geq 1$ ? (Thinking)

 

[I like Serena]

Is it $\lg^2 n \geq 0, \forall n \geq 1$ ? (Thinking)

That's better. (Mmm)

 

[evinda]

That's better. (Mmm)

So, at the end of the exercise, can we take $n_2=\max \{ n_0,n_1,1\}$ ? (Thinking)

 

[I like Serena]

So, at the end of the exercise, can we take $n_2=\max \{ n_0,n_1,1\}$ ? (Thinking)

I guess so yes. (Smile)

 

[evinda]

When we have the definition:

Let $f,g$ asymptotically positive functions. We say that $f=\omega(g)$ if $\forall c>0 \exists n_0=n_0(c) \in \mathbb{N}: \forall n \geq n_0$:

$$0 \leq c g(n)< f(n)$$

do we include $0$ at the values that $n_0$ can take or not? (Thinking)

 

[I like Serena]

When we have the definition:

Let $f,g$ asymptotically positive functions. We say that $f=\omega(g)$ if $\forall c>0 \exists n_0=n_0(c) \in \mathbb{N}: \forall n \geq n_0$:

$$0 \leq c g(n)< f(n)$$

do we include $0$ at the values that $n_0$ can take or not? (Thinking)

We "pick" $n_0$ ourselves, so we are free to include 0 or not.
Generally, we pick $n_0$ a big as we need to, and there is little point in considering to make it 0. (Mmm)

 

[evinda]

We "pick" $n_0$ ourselves, so we are free to include 0 or not.
Generally, we pick $n_0$ a big as we need to, and there is little point in considering to make it 0. (Mmm)

A ok! (Nod) In order that $2^{2^{n+1}}=\omega(2^{2^n})$, it should be:
$$2^{2^{n+1}}> c \cdot 2^{2^n} \geq 0$$

Do I have to say at the beginning that $c \cdot 2^{2^n} \geq 0, \forall n \geq 0$ ? (Thinking)

 

[I like Serena]

A ok! (Nod) In order that $2^{2^{n+1}}=\omega(2^{2^n})$, it should be:
$$2^{2^{n+1}}> c \cdot 2^{2^n} \geq 0$$

Do I have to say at the beginning that $c \cdot 2^{2^n} \geq 0, \forall n \geq 0$ ? (Thinking)

In your definition you have the condition that "f,g asymptotically are positive functions".
That makes what you're suggesting to say sort of redundant.
Although you may indeed want to indicate that you can apply your definition of the $\omega$ symbol. (Nerd)Actually, the definition as wikipedia gives it, is more general since the functions do not have to be positive.
Instead it is required that $c |g(n)| \le |f(n)|$. (Wasntme)