Hell guys, today I gonna teach you to do linear time FFT.
Below is the problem:
Q) Given array of n integers, do First Four Traversal on array.
eg. array is [1, 2, 3, 4, 5, 6, 2, 1], then FFT of array is [1, 2, 3, 4].
So in first, it look very dangerous problem, but on meticulous scrutiny of the underlying scheme, we find easy solution.
- So to solve, we iterate over the array from left to right. While left to right is happening, store first 5 elements of array in an array x[5] = [1, 2, 3, 4, 5].
For those thinking why 5, there is actually a very high IQ reason behind it. So maybe not everyone get it, so I not telling it in this blog.
- Now what we are gonna doing is, we are find the circular-convolution of the array with itself, xc = x[0:5] ⋆ x[0:5]. This is the very easy technique, so I hope all will be able to find auto-circular convolution.
For up example, xc[5] = [45, 50, 50, 45, 355].
Now we will using the easy technique: Discrete Fourier Transform (DFT) to calculate X(5) of xc[5]. This step is easy so I am skip
Next we can find the square root of X(5) and take the inverse DFT of the sequence i[5].
Then we can simply print the first 4 element of i[5].
For those thinking why 4, there is actually a very high IQ reason behind it. So maybe not everyone get it, so I not telling it in this blog.
Prove of algorithm: Got same output. Hence proofed.
Time complexity analysis: Linear