Suppose we are give a natural number n the value of sin(x) and cos(x). How efficiently we can 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 * logn * n