FFT algorithms are faster ways of doing DFT. It is a family of algorithms and not a single algorithm. How it becomes faster can be explained based on the heart of the algorithm: Divide And Conquer. So rather than working with big size Signals, we divide our signal into smaller ones, and perform DFT of these smaller signals. At the end we add all the smaller DFT to get actual DFT of the big signal. This gives great benefit asymptotically. So for large values of N, we save a lot!! We shall see how much in a while.

Let us try to understand it more with little bit of high school maths:

DFT computation for N point signal takes: N^2 multiplications (this is clear from the basic defintion, you have N points, and for each of the points you have to multiply N complex sinusoids).

Now if we dvivide our N-point signal into two signals S1 and S2 of length N/2, and then perform DFT of these smaller signals, we will be doing (N/2)^2 multiplication for each of the S1 and S2. So total no. of mulitplications performed in calculating DFT of S1 and S2 will be 2 * (N/2)^2. Then to get actual DFT of N point signal we need to add these componets. So we can see that we actually need approximately (see Note below) 2 * (N/2)^2= (n^2)/2 which is half that in case of N point signal.

This reduction of half is a result of dividing the siganls once. But if we continue deviding the signals again and again, we will end up in reducing the amount of computations in each step by an amount which is much lesser than N^2. In fact the over all no. of compuations using this method comes of the order of N*logN.

To get an idea of how fast this is as compared to direct DFT, consider a computer which can execute 1 mulitiplication operation in 1 nano-seconds. Assume that we have a signal having total of N= 10^9 points.

Total number of nanoseconds spent for evaluating DFT by direct method (i.e not using FFT)on the given PC= N^2= 10 ^ 18 Nano seconds, which is approximately 31 years. While using FFT we shall spent N*logN = (10^9) *log (10^9)= (10^9)9log10 = (10^9)9 3.32 which is approximately equal to 30 * (10^9) or approximately 30secs!!

So using direct DFT you will spend 31 years while using the devide and conquer approach as in FFT you will get the same output only in 3o seconds!! Now its up to you which method will you prefer :-).

The bottom line is that a lot of problem in nature can be solved much easily if they are small in size. The total effort in solving many small sized problems, is often much smaller than in case of solving one big problem; especially, if the size of the problem is very big such as the above example explained.
This is the basic idea on which FFT algorithms are based upon.

Note: I said approximately because it truns out that we cannot add them directly, and indeed we need a mulitplication factor, actually a phase factor, before combining them. But this is still much lesser that no. of multiplicatiosns we need to do in calculating DFT of S1 and S2, so we can neglect this additional multiplication for larg values of N.

Dvide and Conquer: an anology in military

The concept has been used historically in military. For example Sun Tzu (c. 6th century BCE) a Chinese general, military strategist, and author of The Art of War, writes:

It is the rule in war,

1- if ten times the enemy's strength, surround them;

2- if five times, attack them;

3- if double, be able to divide them;

4- if equal,engage them;

5- if fewer, be able to evade them;

6- if weaker, be able to avoid them.

FFT works on rule no. 3. Rule 1 and 2 tells that if your computer is very powerful enough, then probably you will not be interested in adopting any 'Dvide and Conquer' approach, becasue the gain in doing so will be very less. Also rule no 4 to 6 tells that when your computer is too weak, forget about conquering the problem, by dividing the problem size. You will have to search some other ways. One such way could be Randomization