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 xc = x[0:5] ⋆ x[0:5]. This is the very easy technique, so I hope all will be able to find auto-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