Skip to main content
2 of 2
added 28 characters in body
xskxzr
  • 7.6k
  • 5
  • 23
  • 47

Complexity of calculating sin(nx)

Suppose we are give a natural number $n$, the value of $\sin(x)$ and $\cos(x)$. How efficiently can we compute $\sin(n x)$?

My Thoughts :
The $\sin (n x)$ expansion will have $O(n)$ terms. The power terms will take $\log(n)$ time each to compute. But there will be a term $nC_n/2$ so if $n=10$ this will be $10/5$. How to find the complexity of this term? Is it $\Theta(2^n)$? Is there any alternate algorithm to compute it more efficiently? This way it looks around $2^n n\log n $.