Relation between the functions

[evinda]

Hello! (Smile)I want to determine if $\sqrt{n}$ is $\Theta $ / $O$ / $\Omega$, $o$, $\omega$ of $n^{\sin n}$.

To do so we could calculate the limit:

$$\lim_{n \to +\infty} \frac{\sqrt{n}}{n^{\sin n}}$$

right? But how can we find the limit, although $\lim_{n \to +\infty} \sin n$ does not exist?
Or do we have to determine the relation between $\sqrt{n}$ and $n^{\sin n}$ in an other way? (Thinking)

 

[Fallen Angel]

Hi,

I don't know how to solve that exercise, but $\underset{n\to \infty}{lim}\dfrac{\sqrt{n}}{n^{sin \ n}}$ doesn't exist, so you will need to find another method to solve the exercise.

Taking a little look at the definitions I think it is not $O \ or \ o$.

I think it could be $\Omega$ since the upper limit of that sequence seems to be infinity, but you will need to check it carefully.

 

[evinda]

I found that none of the relations:

$$\sqrt{n}=O(n^{\sin n}) \\ \sqrt{n}=o(n^{\sin n}) \\ \sqrt{n}=\Omega(n^{\sin n}) \\ \sqrt{n}=\omega(n^{\sin n})$$

hold. But how could we prove this? (Thinking)

 

[I like Serena]

I found that none of the relations:

$$\sqrt{n}=O(n^{\sin n}) \\ \sqrt{n}=o(n^{\sin n}) \\ \sqrt{n}=\Omega(n^{\sin n}) \\ \sqrt{n}=\omega(n^{\sin n})$$

hold. But how could we prove this? (Thinking)

Hey! ;)

Let's do a proof of contradiction, using the definition of $O$. (Thinking)

Suppose $\sqrt{n}=O(n^{\sin n})$, then $\sqrt{n} \le k\cdot n^{\sin n}$ for some $k$ and sufficiently large $n$.
Or in other words $\frac{\sqrt{n}}{n^{\sin n}} \le k$ for some $k$ and sufficiently large $n$.

However large we pick $n_0$, we can always find an $n \ge n_0$ for which $\sin n$ is arbitrarily close to either $-1$ or $+1$ . That is because the period of the $\sin$ is an irrational number.
So we can for instance always find an $n$ for which $\sin n < -0.9$.

For that $n$ we have:
$$\frac{\sqrt{n}}{n^{\sin n}} >\frac{\sqrt{n}}{n^{-0.9}} = n^{0.9}\sqrt{n}$$
The right hand side can always be larger than any constant $k$, which is a contradiction.

So $\sqrt{n}\ne O(n^{\sin n})$. (Nerd)

 

[evinda]

Hey! ;)

Let's do a proof of contradiction, using the definition of $O$. (Thinking)

Suppose $\sqrt{n}=O(n^{\sin n})$, then $\sqrt{n} \le k\cdot n^{\sin n}$ for some $k$ and sufficiently large $n$.
Or in other words $\frac{\sqrt{n}}{n^{\sin n}} \le k$ for some $k$ and sufficiently large $n$.

However large we pick $n_0$, we can always find an $n \ge n_0$ for which $\sin n$ is arbitrarily close to either $-1$ or $+1$ . That is because the period of the $\sin$ is an irrational number.
So we can for instance always find an $n$ for which $\sin n < -0.9$.

Could you explain me further why we can always find an $n$ for which $\sin n < -0.9$ ? (Thinking)

For that $n$ we have:
$$\frac{\sqrt{n}}{n^{\sin n}} >\frac{\sqrt{n}}{n^{-0.9}} = n^{0.9}\sqrt{n}$$
The right hand side can always be larger than any constant $k$, which is a contradiction.

So we have found that

$$\frac{\sqrt{n}}{n^{\sin n}} >\frac{\sqrt{n}}{n^{-0.9}} = n^{0.9}\sqrt{n}$$and $n^{0.9}\sqrt{n} \to +\infty$.

So since $\frac{\sqrt{n}}{n^{\sin n}}>n^{0.9}\sqrt{n}$ don't we conclude that $\frac{\sqrt{n}}{n^{\sin n}} \to +\infty$ , i.e. that $n^{\sin n}=o(\sqrt{n})$ ? Or am I wrong?

 

[I like Serena]

Could you explain me further why we can always find an $n$ for which $\sin n < -0.9$ ? (Thinking)

Not really at this time. Not without doing some research first. (Worried)

I merely know that $n \bmod 2\pi$ gets arbitrarily close to any number in the interval $[0, 2\pi)$, and it does so infinitely many times for numbers bigger than any arbitrary number.
That's a consequence of $\pi$ being irrational. (Wasntme)

So we have found that

$$\frac{\sqrt{n}}{n^{\sin n}} >\frac{\sqrt{n}}{n^{-0.9}} = n^{0.9}\sqrt{n}$$and $n^{0.9}\sqrt{n} \to +\infty$.

So since $\frac{\sqrt{n}}{n^{\sin n}}>n^{0.9}\sqrt{n}$ don't we conclude that $\frac{\sqrt{n}}{n^{\sin n}} \to +\infty$ , i.e. that $n^{\sin n}=o(\sqrt{n})$ ? Or am I wrong?

Not quite, we only know that for every $n_0$ we can always find an $n_1 > n_0$ such that $\frac{\sqrt{n_1}}{n_1^{\sin n_1}}>n_1^{0.9}\sqrt{n_1}$.
It's not true for every $n \ge n_1$. To the contrary, since the $\sin$ can also get arbitrarily close to $1$ instead of $-1$. (Wasntme)

 

[evinda]

Not quite, we only know that for every $n_0$ we can always find an $n_1 > n_0$ such that $\frac{\sqrt{n_1}}{n_1^{\sin n_1}}>n_1^{0.9}\sqrt{n_1}$.
It's not true for every $n \ge n_1$. To the contrary, since the $\sin$ can also get arbitrarily close to $1$ instead of $-1$. (Wasntme)

So is the following right? (Thinking)

Suppose $\sqrt{n}=o(n^{\sin n})$.

Then $\forall c>0, \exists n_0 \in \mathbb{N}$ such that $\sqrt{n} < c\cdot n^{\sin n}, \forall n \geq n_0$.

Or in other words $\frac{\sqrt{n}}{n^{\sin n}} <c $ for all $c>0$ and sufficiently large $n$.

However large we pick $n_0$, we can always find an $n \ge n_0$ for which $\sin n$ is arbitrarily close to either $-1$ or $+1$ . That is because the period of the $\sin$ is an irrational number.
So we can for instance always find an $n$ for which $\sin n < -0.9$.

For that $n$ we have:
$$\frac{\sqrt{n}}{n^{\sin n}} >\frac{\sqrt{n}}{n^{-0.9}} = n^{0.9}\sqrt{n}$$
The right hand side can always be larger than any constant $k$, which is a contradiction.

Thus, $\sqrt{n} \neq o(n^{\sin n})$.From the fact that $\sqrt{n} \neq o(n^{\sin n})$ we conclude that $\sqrt{n} \neq O(n^{\sin n})$.Now suppose that $\sqrt{n}=\omega(n^{\sin n})$.Then $\forall c>0, \exists n_0 \in \mathbb{N}$ such that $\sqrt{n}> c n^{\sin n}, \forall n \geq n_0$.Or in other words $\frac{\sqrt{n}}{n^{\sin n}}>c$ for all $c$ and sufficiently large $n$.However large we pick $n_0$, we can always find an $n \ge n_0$ for which $\sin n$ is arbitrarily close to either $-1$ or $+1$ .

So we can for instance always find an $n$ for which $\sin n >0.9$.

For that $n$ we have:
$$\frac{\sqrt{n}}{n^{\sin n}} <\frac{n^{0.5}}{n^{0.9}} = \frac{1}{n^{0.4}}$$
The right hand side can always be smaller than any constant $k$, which is a contradiction.

Thus, $\sqrt{n} \neq \omega(n^{\sin n}) \Rightarrow \sqrt{n} \neq \Omega(n^{\sin n})$.

 

[I like Serena]

Looks good to me! (Nod)

Since you've introduced the constant $c$ instead of $k$, I'd replace all occurences of $k$ by $c$ though. (Nerd)

And perhaps you should mention for $\omega$, at the end, that $c > 0$. (Nerd)

And in retrospect I realized that it would be good to introduce, say, $n_1$ for the value greater than $n_0$ that satisfies the criterion. That's to avoid any confusion with the $n$ that might take any value. (Nerd)

 

[evinda]

Looks good to me! (Nod)

Since you've introduced the constant $c$ instead of $k$, I'd replace all occurences of $k$ by $c$ though. (Nerd)

And perhaps you should mention for $\omega$, at the end, that $c > 0$. (Nerd)

And in retrospect I realized that it would be good to introduce, say, $n_1$ for the value greater than $n_0$ that satisfies the criterion. That's to avoid any confusion with the $n$ that might take any value. (Nerd)

Nice! (Smirk) Do I have to justify the following or is it known?

However large we pick $n_0$, we can always find an $n \geq n_0$ for which $\sin n$ is arbitrarily close to either $-1$ or $+1$ .
So we can for instance always find an $n$ for which $\sin n <-0.9$.

 

[I like Serena]

Nice! (Smirk) Do I have to justify the following or is it known?

However large we pick $n_0$, we can always find an $n \geq n_0$ for which $\sin n$ is arbitrarily close to either $-1$ or $+1$ .
So we can for instance always find an $n$ for which $\sin n <-0.9$.

I consider it known, but I guess for a proper proof you need a reference to some proposition or some such. How much have you learned about irrational numbers? Is there some such proposition in there? (Wondering)

 

[evinda]

I consider it known, but I guess for a proper proof you need a reference to some proposition or some such. How much have you learned about irrational numbers? Is there some such proposition in there? (Wondering)

We haven't said something about irrational numbers in the course Algorithms and Complexity.. So should I just say it like that or explain it further?

Now I realized something... (Wait)$$f(n) \neq o(g(n)) \text{ doesn't imply that } f(n) \neq O(g(n))$$

but:

$$f(n) \neq O(g(n)) \text{ implies that } f(n) \neq o(g(n))$$

 

[I like Serena]

We haven't said something about irrational numbers in the course Algorithms and Complexity.. So should I just say it like that or explain it further?

For a course in Algorithms and Complexity I'd just say it like that. (Wasntme)
If it were an advanced algebra course, perhaps it should be explained further.

Now I realized something... (Wait)$$f(n) \neq o(g(n)) \text{ doesn't imply that } f(n) \neq O(g(n))$$

but:

$$f(n) \neq O(g(n)) \text{ implies that } f(n) \neq o(g(n))$$

Oh yes, you are right! (Blush)

 

[evinda]

Suppose $\sqrt{n}=O(n^{\sin n})$.
That means that $\exists c>0, n_0 \in \mathbb{N}$ such that $\forall n \geq n_0$:

$\sqrt{n} \leq c n^{\sin n}$.

Or in other words $\frac{\sqrt{n}}{n^{\sin n}} \le c$ for some $c$ and for a sufficiently large $n$.

However large we pick $n_0$, we can always find an $n_1 \ge n_0$ for which $\sin n_1$ is arbitrarily close to $-1$ .
So we can always find an $n_1$ for which $\sin{n_1} < -0.9$.

Then we have:

$$\frac{\sqrt{n_1}}{n^{\sin n_1}} >\frac{\sqrt{n_1}}{n_1^{-0.9}} = n_1^{0.9}\sqrt{n_1}=n_1^{1.4}$$Can the right hand side always be larger than any constant $c$ or than a specific constant? (Thinking)

 

[I like Serena]

Or in other words $\frac{\sqrt{n}}{n^{\sin n}} \le c$ for some $c$ and for a sufficiently large $n$.

That should be: any sufficiently large $n$. (Nerd)

$$\frac{\sqrt{n_1}}{n^{\sin n_1}} >\frac{\sqrt{n_1}}{n_1^{-0.9}} = n_1^{0.9}\sqrt{n_1}=n_1^{1.4}$$

Can the right hand side always be larger than any constant $c$ or than a specific constant? (Thinking)

Pick any constant $c$.
Then actually, it might be possible that for a specific $n_1$ the RHS is smaller than $c$. (Doh)
To cover that case we need to pick $n_0$ large enough so that $n_0^{1.4} > c$. Then the required result follows without change. (Wasntme)

 

[evinda]

That should be: any sufficiently large $n$. (Nerd)

Pick any constant $c$.
Then actually, it might be possible that for a specific $n_1$ the RHS is smaller than $c$. (Doh)
To cover that case we need to pick $n_0$ large enough so that $n_0^{1.4} > c$. Then the required result follows without change. (Wasntme)

Great! Thank you very much! (Party)