| 1 |
We can now apply the same idea recursively; chop off the lowest binary digit of k so as to derive a formula for each FFT in terms of two more half the size.
|
| 2 |
Let C(N) be computational complexity of the FFT of size N
|
| 3 |
Let Tbutterfly = 2T+ + T* be the time to calculate fE and fO for one value of m-
|
| 4 |
Here T+ is time for a complex addition and T* the time for a complex multiplication.
|
| 5 |
We assume that complex number TN(m-) has been precalculated and is available by table lookup
|
| 6 |
Then C(N) = 2C(N/2) + (N/2) Tbutterfly
|
| 7 |
This can be solved as C(N) = NlogNTbutterfly/2
|
