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

[evinda]

Suppose you check the condition for this to be true.
Is it (always) satisfied with what you have? (Wondering)

Is it not always satisfied? (Thinking)

 

[evinda]

Could you give me a hint what might be wrong? (Thinking)

 

[I like Serena]

Is it not always satisfied? (Thinking)

Could you give me a hint what might be wrong? (Thinking)

I have lost track of what was going on in this thread.
Can you restate what you're trying to proof and what you have found? (Wondering)

 

[evinda]

I have lost track of what was going on in this thread.
Can you restate what you're trying to proof and what you have found? (Wondering)

We want to prove that $\lg^2 n=o(2^{\sqrt{2 \lg n}})$, so we want to prove that: $\forall c>0, \exists n_0$, such that $\forall n \geq n_0: \lg^2 n< c \cdot 2^{\sqrt{2 \lg n}}$

$\lg^2 n< c \cdot 2^{\sqrt{2 \lg n}} \Rightarrow \lg{ \lg^2 n}<\lg{(c \cdot 2^{\sqrt{2 \lg n}})}=\lg c+\lg{2^{\sqrt{2 \lg n}}}=\lg c+ \sqrt{2 \lg n} \\ \Rightarrow \lg {\lg^2 n}< \lg c+ \sqrt{2} \sqrt{\lg n}$

We set $y=\lg n$.

$$\lg{ \lg^2 n}<\lg c+ \sqrt{2} \sqrt{\lg n} \Rightarrow \lg{ y^2}< \lg c+ \sqrt{2} \sqrt{y} \Rightarrow 2 \lg y< \lg c+ \sqrt{2} \sqrt{y}$$

$$\lim_{y \to +\infty} \frac{2 \lg{ y}}{\lg c+ \sqrt{2} \sqrt{y}}=\lim_{y \to +\infty} \frac{\frac{2}{y}}{ \frac{1}{ \sqrt{2} \sqrt{y}}}=\lim_{y \to +\infty} \frac{2 \sqrt{2} \sqrt{y}}{y}=lim_{y \to +\infty} \frac{2 \sqrt{2}}{\sqrt{y}}=0$$

What can I say about the limit, now that we have $y$ and not $n$ ? (Thinking)

 

[I like Serena]

We set $y=\lg n$.

$$\lg{ \lg^2 n}<\lg c+ \sqrt{2} \sqrt{\lg n} \Rightarrow \lg{ y^2}< \lg c+ \sqrt{2} \sqrt{y} \Rightarrow 2 \lg y< \lg c+ \sqrt{2} \sqrt{y}$$

$$\lim_{y \to +\infty} \frac{2 \lg{ y}}{\lg c+ \sqrt{2} \sqrt{y}}=\lim_{y \to +\infty} \frac{\frac{2}{y}}{ \frac{1}{ \sqrt{2} \sqrt{y}}}=\lim_{y \to +\infty} \frac{2 \sqrt{2} \sqrt{y}}{y}=lim_{y \to +\infty} \frac{2 \sqrt{2}}{\sqrt{y}}=0$$

What can I say about the limit, now that we have $y$ and not $n$ ? (Thinking)

We can back substitute $y=\lg n$ to find:
$$\lim_{n \to +\infty} \frac{2 \lg( \lg n)}{\lg c+ \sqrt{2} \sqrt{\lg n}}=0$$

Next is writing out what this means in terms of $\epsilon$ and $n_0$. (Wasntme)

 

[evinda]

We can back substitute $y=\lg n$ to find:
$$\lim_{n \to +\infty} \frac{2 \lg( \lg n)}{\lg c+ \sqrt{2} \sqrt{\lg n}}=0$$

Next is writing out what this means in terms of $\epsilon$ and $n_0$. (Wasntme)

So, could we say it like that? (Thinking)

$$\lim_{y \to +\infty} \frac{2 \lg y}{\lg c+ \sqrt{2} \sqrt{y}}=0 \Rightarrow \lim_{n \to +\infty} \frac{2 \lg {\lg n}}{\lg c+ \sqrt{2} \sqrt{\lg n}}=0$$

That means that $\forall \epsilon>0, \exists n_0$, such that $\forall n \geq n_0$:

$$2 \lg {(\lg n)}< \epsilon (\lg c+ \sqrt{2} \sqrt{\lg n}) \Rightarrow \lg{\lg^2 n}< \epsilon(\lg c+ \sqrt{2 \lg n})$$

 

[I like Serena]

So, could we say it like that? (Thinking)

$$\lim_{y \to +\infty} \frac{2 \lg y}{\lg c+ \sqrt{2} \sqrt{y}}=0 \Rightarrow \lim_{n \to +\infty} \frac{2 \lg {\lg n}}{\lg c+ \sqrt{2} \sqrt{\lg n}}=0$$

That means that $\forall \epsilon>0, \exists n_0$, such that $\forall n \geq n_0$:

$$2 \lg {(\lg n)}< \epsilon (\lg c+ \sqrt{2} \sqrt{\lg n}) \Rightarrow \lg{\lg^2 n}< \epsilon(\lg c+ \sqrt{2 \lg n})$$

Yes, but with a slight correction. (Wait)

It means that $\forall \epsilon>0, \exists n_0$, such that $\forall n \geq n_0$:
$$\left|\frac{2 \lg {(\lg n)}}{\lg c+ \sqrt{2} \sqrt{\lg n}}\right|< \epsilon
\Rightarrow 2 \lg {(\lg n)}< \epsilon |\lg c+ \sqrt{2} \sqrt{\lg n}|
\Rightarrow \lg{\lg^2 n}< \epsilon|\lg c+ \sqrt{2 \lg n}|$$

The distinction with absolute sign is necessary because $\lg c$ can be negative.

 

[evinda]

Yes, but with a slight correction. (Wait)

It means that $\forall \epsilon>0, \exists n_0$, such that $\forall n \geq n_0$:
$$\left|\frac{2 \lg {(\lg n)}}{\lg c+ \sqrt{2} \sqrt{\lg n}}\right|< \epsilon
\Rightarrow 2 \lg {(\lg n)}< \epsilon |\lg c+ \sqrt{2} \sqrt{\lg n}|
\Rightarrow \lg{\lg^2 n}< \epsilon|\lg c+ \sqrt{2 \lg n}|$$

The distinction with absolute sign is necessary because $\lg c$ can be negative.

A ok! (Nod) But, could we continue now? (Thinking)

 

[I like Serena]

A ok! (Nod) But, could we continue now? (Thinking)

Didn't we already do that?
What do you think comes next? (Wondering)

 

[evinda]

Didn't we already do that?
What do you think comes next? (Wondering)

We set $\epsilon=1$ and then we have that $\exists n_0 \geq 0$, such that $\forall n \geq n_0$: $\lg{ \lg^2 n}< |\lg c+ \sqrt{2 \lg n}|$.

Do we have to continue like that?

$\lg{ \lg^2 n}< |\lg c+ \sqrt{2 \lg n}| \Rightarrow \lg c+\sqrt{2 \lg n}> \lg {\lg^2 n} \text{ or } \lg c+ \sqrt{2 \lg n}< - \lg{ \lg^2 n} $

And can we conclude from that, that $\exists n_0$ such that $\forall n \geq n_0$:
$$\lg{ \lg^2 n }< \lg c+ \sqrt{2 \lg n}$$

?
(Thinking)

 

[I like Serena]

We set $\epsilon=1$ and then we have that $\exists n_0 \geq 0$, such that $\forall n \geq n_0$: $\lg{ \lg^2 n}< |\lg c+ \sqrt{2 \lg n}|$.

If we pick $n_0$ large enough (we can introduce $n_1$ if you want), then $\lg c+ \sqrt{2 \lg n} >0$.
It follows that then:
$$\lg{ \lg^2 n}< \lg c+ \sqrt{2 \lg n}$$
(Wasntme)

 

[evinda]

If we pick $n_0$ large enough (we can introduce $n_1$ if you want), then $\lg c+ \sqrt{2 \lg n} >0$.
It follows that then:
$$\lg{ \lg^2 n}< \lg c+ \sqrt{2 \lg n}$$
(Wasntme)

So, can we say it like that? (Thinking)

We set $\epsilon=1$ and then we have that $\exists n_0 \geq 0$, such that $\forall n \geq n_0$: $\lg{ \lg^2 n}< |\lg c+ \sqrt{2 \lg n}|$.

We pick a large enough $n_1$, such that $\lg c+ \sqrt{2 \lg n}>0, \forall n \geq n_1$.

Now, we pick $n_2=\max \{ n_1, n_0 \}$ and we have that:

$\forall n \geq n_2: \lg{ \lg^2 n}< \lg c+ \sqrt{2 \lg n}$.

 

[I like Serena]

So, can we say it like that? (Thinking)

We set $\epsilon=1$ and then we have that $\exists n_0 \geq 0$, such that $\forall n \geq n_0$: $\lg{ \lg^2 n}< |\lg c+ \sqrt{2 \lg n}|$.

We pick a large enough $n_1$, such that $\lg c+ \sqrt{2 \lg n}>0, \forall n \geq n_1$.

Now, we pick $n_2=\max \{ n_1, n_0 \}$ and we have that:

$\forall n \geq n_2: \lg{ \lg^2 n}< \lg c+ \sqrt{2 \lg n}$.

Yes we can! (Nod)

 

[evinda]

Yes we can! (Nod)

So, we have shown now that $\lg^2 n=o(2^{\sqrt{2 \lg n}})$, right? (Smile)

 

[I like Serena]

So, we have shown now that $\lg^2 n=o(2^{\sqrt{2 \lg n}})$, right? (Smile)

Yep! (Nod)

 

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