Option A is correct. θ(nlgn)
Explanation:
fast Fourier Transformation (FFT) is raised due to the high cost in FT. In FFT calculations taken place by divide and conquer method, which will make the entire calculation into a graph like form then compute. So it will take lg n time and and there will be n degree graph.