The Computational Complexity of DIF FFT

• 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

Previous slide

Next slide

Back to first slide

View graphic version