Comparing Growth rates

142 Views Asked by At

Compare the growth rates of two functions $$ \begin{aligned} f(n) & = n |\sin \pi n/2| + 1 \\ g(n) & = \sqrt{n} \end{aligned} $$

I found this stack exchange post Growth rate of $n^{\sin n}$

And I think this is not comparable as $1 \leq f(n) \leq \infty$ as $n\rightarrow \infty$.

I am wondering if my thought is correct.

1

There are 1 best solutions below

1
On BEST ANSWER

If you are talking about asymptotic comparisons, then they are not comparable. Notice that $|\sin(\pi n/2)|=0$ when $n$ is even, and $|\sin(\pi n/2)|=1$ when $n$ is odd. So $f(n)/g(n)$ oscillates between $0$ (take limit when $n$ is even) and $+\infty$ (take limit when $n$ is odd). More precisely, $\liminf_{n\to\infty}(f(n)/g(n))=0$ and $\limsup_{n\to\infty}(f(n)/g(n))=+\infty$. The situation is the same for $g(n)/f(n)$.