Big O with cosine?

Question

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?

Your conclusions are correct. Should perhaps mention why $f(n)$ is $0$ infinitely often. — André Nicolas, Feb 25 '14 at 08:19

score 2 · Answer 1 · answered Feb 25 '14 at 08:19

2

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?

answered Feb 25 '14 at 08:19

5xum

123,496
6
128
204

score 2 · Answer 2 · answered Feb 25 '14 at 08:34

2

Note that $f(n) = \left\{\begin{array}{lr} 0: \quad 2\nmid n\\ n: \quad 2\mid n\end{array}\right.$

answered Feb 25 '14 at 08:34

Flowers

775
4
13

Big O with cosine?

2 Answers2