Calculating one value of X(k) in the frequency domain costs N complex multiplications, so calculating all N of them one by one, "starting over" every time, costs N times N is N^2 complex multiplications.
However, if you first calculate the DFT of all even entries ((N/2)^2 multiplications) and all odd entries (another (N/2)^2 multiplications), for a total of N^2 / 2 multiplications, you can calculate the full DFT from those with just another N/2 multiplications and N additions. For large N that last step can be ignored, and thus you gained a factor of two. If N is a power of two N=2^q, then you can repeat this trick q times by doing it also for the smaller DFTs of the even and odd entries, winning q times a factor 2, thus it becomes N^2 / (2^q) = N^2 / N = N multiplications, but you have to do that q = log2(N) times, so in the asymptotical case you end up with something of the order N log(N).
To see why you can combine the DFTs of even and odd entries in such an easy way, you must realize that you're just summing entries multiplied with evenly spaced complex numbers on the unit circle in the complex plane (Nth roots of 1, which all lay on a circle). So, if you treat the odd entries as the only input for some DFT then you you're only a single rotation away from what you need for the full DFT: the rotation to bring the entries back to where they should be. A rotation means a multiplication, hence N/2 extra multiplications before you can combine the two smaller DFTs with just additions.
Note that the same trick can be applied when N doesn't factor into just 2^q, but when it can be factored into many small prime numbers. For example, if N=p^q you can repeat q times a stage where you calculate p DFT's each of N/p points and then combine those with (p-1)N/p multiplications (rotating p-1 of the DFT's of the previous stage) and (p-1)N additions, for each of the q stages.