|
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.
|
|
Let C(N) be computational complexity of the FFT of size N
|
|
Let Tbutterfly = 2T+ + T* be the time to calculate fE and fO for one value of m-
|
|
Here T+ is time for a complex addition and T* the time for a complex multiplication.
|
|
We assume that complex number TN(m-) has been precalculated and is available by table lookup
|
|
Then C(N) = 2C(N/2) + (N/2) Tbutterfly
|
|
This can be solved as C(N) = NlogNTbutterfly/2
|
