Empirically testing whether FWT or FFT is faster. Disclaimer: I don't understand wavelets.
Speed of FFT implementation doesn't care what the data is:
In [23]: a = rand(2**20)
In [24]: timeit fft(a)
10 loops, best of 3: 128 ms per loop
In [25]: a = rand(2**20)
In [26]: timeit fft(a)
10 loops, best of 3: 126 ms per loop
For n = 16, PyWavelets' wavedec() produces n = 16 output samples:
In [12]: wavedec(rand(16),'haar')
Out[12]:
[array([ 2.01424651]),
array([ 0.04603367]),
array([-0.1796771 , -0.01105563]),
array([ 0.39546541, -0.24874957, 0.0585042 , -0.79528743]),
array([-0.18981191, -0.22084216, -0.40538726, 0.2132084 , 0.03739225,
0.11563665, 0.12945121, -0.05167751])]
FFT also produces n = 16 samples for n = 16 input, but they are imaginary numbers, so they contain twice as much information:
In [13]: fft(rand(16))
Out[13]:
array([ 10.74250930+0.j , -0.32003948+0.33706604j,
-0.28726933+0.39145379j, 0.80358538+1.10708532j,
-0.71895673+0.40474147j, 0.02817873+0.3182814j ,
0.76040762+0.04767775j, 0.80168368+0.63285109j,
1.03253191+0.j , 0.80168368-0.63285109j,
0.76040762-0.04767775j, 0.02817873-0.3182814j ,
-0.71895673-0.40474147j, 0.80358538-1.10708532j,
-0.28726933-0.39145379j, -0.32003948-0.33706604j])
So I think RFFT is a more fair comparison:
In [14]: rfft(rand(16))
Out[14]:
array([ 5.44926212+0.j , 0.34752893-0.059578j ,
-0.20744422+0.58657297j, 0.02703663-0.32749533j,
-0.78320357-0.0325825j , -0.69896844-0.16904737j,
0.35829407+1.14605358j, 1.41753916-1.48978497j, 1.04193105+0.j ])
(Anyway, the speed of RFFT is always about twice FFT:)
In [32]: a = rand(2**23)
In [33]: timeit fft(a)
1 loops, best of 3: 1.24 s per loop
In [34]: timeit rfft(a)
1 loops, best of 3: 641 ms per loop
So I did this to compare:
In [35]: a = rand(256)
In [36]: timeit rfft(a)
100000 loops, best of 3: 8.63 us per loop
In [38]: timeit wavedec(a, 'haar')
10000 loops, best of 3: 43.6 us per loop
... etc.
Results of µs computation vs n size:
Power n RFFT FWT
3 8 5.45 22.4
5 32 6.64 27.7
7 128 6.88 36.9
8 256 8.63 43.6
10 1024 22.3 58.4
12 4096 80.5 95.5
13 8192 173 131
16 65536 2160 611
18 262144 14700 4220
20 1048576 72100 18000
23 8388608 603000 146000
Also it varies a lot by wavelet, though:
In [83]: a = rand(2**12)
In [84]: timeit rfft(a)
10000 loops, best of 3: 80.5 us per loop
In [85]: timeit wavedec(a, 'haar')
10000 loops, best of 3: 95.5 us per loop
In [86]: timeit wavedec(a, 'dmey')
1000 loops, best of 3: 551 us per loop
In [89]: timeit wavedec(a, 'db1')
10000 loops, best of 3: 91.5 us per loop
In [90]: timeit wavedec(a, 'db2')
10000 loops, best of 3: 97.3 us per loop
In [93]: timeit wavedec(a, 'coif1')
10000 loops, best of 3: 122 us per loop