[Math] Big O with cosine


Consider the functions $f(n) = n\cdot \max(0,\cos(\pi n))$, $g(n) = n$. What is the relation between these functions in big-$\mathcal O$ notation? Assume $n$ takes on only positive integer values. For the cosine, the angle is being expressed in radians.

How do I compare functions with cosine in them with regards to big $\mathcal O$? I think that $f(n)$ is $\mathcal O(g(n))$ because it is strictly less than or equal to $c\cdot n$ with $c = 1$. In addition, $f(n)$ is not $\Theta(g(n))$ because there is no positive constant $c$ where $g(n)$ is strictly less than or equal to $f(n)$. Is this intuition correct?

Best Answer

Hint: Is there a simpler way to express $\cos(\pi n)$? Take a look at the values of $\cos(\pi n)$ for some values of $n$ ($n=1,2,3,4,5$). Can you find a pattern?

Related Question