Upper and lower bounds for $n|\sin(n)|$

400 Views Asked by At

In asymptotic analysis, we have the following set of functions

\begin{align} O(g) &= \big\{ f:\mathbb{N}\to\mathbb{R} \,|\, \exists C \in \mathbb{R}^+, \, \exists N \in \mathbb{N}^+, \, \forall n\ge N \implies f(n)\le C \, g(n)\big\}, \\ \Omega(g) &= \big\{ f:\mathbb{N}\to\mathbb{R} \,|\, \exists C \in \mathbb{R}^+, \, \exists N \in \mathbb{N}^+, \, \forall n\ge N \implies C \, g(n) \le f(n) \big\}, \\ \Theta(g) &= \big\{ f:\mathbb{N}\to\mathbb{R} \,|\, \exists C_1,C_2 \in \mathbb{R}^+, \, \exists N \in \mathbb{N}^+, \forall n\ge N \implies C_1 \, g(n) \le f(n) \le C_2 \, g(n) \big\}. \end{align}

Intuitively speaking, for enough large $n$, $O(g)$ represents the set of all functions which are bounded above by $g$ and $\Omega(g)$ represents the set of all functions bounded below by $g:\mathbb{N}\to\mathbb{R}$. Furthermore, it is obvious that $\Theta(g) = O(g) \cap \Omega(g)$. Consider the following functions

$$f:n\to n, \qquad g: n \to n^2|\sin(n)|.$$

I want to investigate the assertions $f \in O(g)$ and $f \in \Omega(g)$ for the aforementioned functions. For $f\in\Omega(g)$ to hold, it is required that

$$C \, n^2|\sin(n)|\le n \iff n|\sin(n)| \le \frac{1}{C}. \tag{1}$$

Intuitively, we can say that $n|\sin(n)|$ is not bounded above by any constant value. However, I couldn't write down a nice mathematical argument for it. For $f\in O(g)$ to hold, it is required that

$$n \le C \, n^2|\sin(n)| \iff \frac{1}{C} \le n|\sin(n)|, \tag{2}$$

which is equivalent to asking whether $n|\sin(n)|$ has a positive lower bound or not. Again, I couldn't write down a precise mathematical argument for this one. For both cases, it would be easy to write such an argument if $n\in\mathbb{R}^+$ by choosing $n$ to be $2k\frac{\pi}{2}$ or $(2k+1)\frac{\pi}{2}$. Below is also a graphical illustration for the case of $n\in\mathbb{R}^+$. However, we know that $n\in\mathbb{N}$.

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

Hint: Since $\pi$ is irrational you can find arbitrarily large integers $n$ and $m$ such that $$|m \pi - n| < 1/m$$ This is a result of the Dirichlet's approximation theorem or Diophantine approximation.

Now show this $n$ is close enough to $m \pi$ so that $n \sin n$ is small for such $n$ (in particular bounded).

Now for the same values of $n$ show that $\sin(n+1)$ is not too small so $(n+1) \sin(n+1)$ is big.