The [Fast Fourier Transform][1] takes O(*N* log *N*) operations, while the [Fast Wavelet Transform][2] takes O(*N*).  But what, specifically, does the FWT compute?

Although they are often compared, it seems like the FFT and FWT are apples and oranges.  As I understand it, a more appropriate comparison would be the STFT (FFTs of small chunks over time) and the complex Morlet WT, since they're both time-frequency representations based on complex sinusoids (please correct me if I'm wrong).  This is often shown with a diagram like this:

![Grids showing how the coefficients of the FFT and WT correspond to the time-frequency plane][3]

([Another example][4])

The left shows how the STFT is a bunch of FFTs stacked on top of each other as time passes (this representation is the origin of the [spectrogram][5]), while the right shows the dyadic WT, which has better time resolution at high frequencies and better frequency resolution at low frequencies (this representation is called a [scalogram][6]).  In this example, *N* for the STFT is the number of vertical columns, and a single O(*N* log *N*) FFT operation calculates a single row of *N* coefficients from *N* samples.

What I don't understand:  How many coefficients does a single O(*N*) FWT operation compute, and where are they located on the time-frequency chart above?  Which rectangles get filled in by a single computation?

If we calculate an equal-area block of time-frequency coefficients using both, do we get the same amount of data out?  Is the FWT still more efficient than the FFT?

Concrete example using [PyWavelets][7]:

    In [2]: dwt([1, 0, 0, 0, 0, 0, 0, 0], 'haar')
    Out[2]:
    (array([ 0.70710678,  0.        ,  0.        ,  0.        ]),
     array([ 0.70710678,  0.        ,  0.        ,  0.        ]))

It creates two sets of 4 coefficients, so it's the same as the number of samples in the original signal.  But what's the relationship between these 8 coefficients and the tiles in the diagram?


  [1]: http://en.wikipedia.org/wiki/Fast_Fourier_transform
  [2]: http://en.wikipedia.org/wiki/Fast_wavelet_transform
  [3]: https://i.sstatic.net/i7V58.png
  [4]: http://www.ndt.net/article/v07n09/08/fig4.gif
  [5]: http://en.wikipedia.org/wiki/Spectrogram
  [6]: http://support.sas.com/rnd/app/da/new/802ce/iml/chap1/sect8.htm
  [7]: http://www.pybytes.com/pywavelets/