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