Why output of FFT is same as input data size ?

Question

What I understand from DFT formula below I can decide the N my self. I can try to use just 16 bins to describe a function or I may even use 4 , it won't be very accurate but I can do it right?

The confusing part is even most thrusted websites say next sentence taken from this link: The most general case allows for complex numbers at the input and results in a sequence of equal length .

That is extremely strange to me because lets say I have 100000 data , and complexity of fourier is Nlog(N), do I have to go with 100000log(100000). Why can't I go with less accurate but more efficient N=16. Why libraries won't implement like this?

Ps: As a computer science graduate I am sorry if my question is not scientific enough but I asked it to stackoverflow, DSP site etc.. but couldn't clear my mind. I hope I made my point this time .

Answer 1

You can certainly use $16$ or $4$ bins, yes. I find it strange that libraries don't implement arbitrary bin counts, but I suppose I would shrug and say it's probably because they're written for people dealing with much more data than you.

(Unless you're just trying to use 16 bins for large data sets for your own amusement, but then you should probably be writing your own DFT functions :P )

Answer 2

You are confusing the length of the sequence of values and the amount of computation to get the Fourier transform. The definition of the Fourier transform (fast or not) takes $N$ values in time and returns $N$ values in frequency. If $N$ is a power of $2$, the FFT allows you to do a number of floating point operations that scales as $N \log N$ to get the result. A naive Fourier transform routine would take $N^2$ operations. The result will be the same either way. The FFT is clever in using repeatable sections of the calculation to improve efficiency. For $N=16, N \log N=64, N^2=256$ only a factor of $4$ different. But for $N=2^{16}=65,536, N \log N=2^{20}=1,048,576$, while $N^2=2^{32}=4,294,967,296$, or $4,096$ times higher.