Fast Fourier Transform, Algorithms, Pattern Matching, Convolution, Combination Sum.
of X is such that: Then we can calculate the C vector as follows: This is known as the Inverse Fourier Transform. We can compute the inverse fourier transform using the same FFT algorithm in O(nlogn) time complexity. Instead of the coefficients a in p(x) or b in q(x) we are using the computed