Fourier Transform, Optical Computing, Technology, Next Generation Tech.
3(N-1)​ real additions. Step 2 requires us to append K-N zeros to a vector. In practice, one may directly store the result of step 1 in a larger array pre-filled with zeros. Step 4 simply involves reading N elements from an array. So, steps 1, 2, 4, and 5 all have a linear complexity in ​K. Step 3