Suppose you have two programs for computing the DFT of a sequence x[n] that has N = 2^v nonzero samples. Program A computes the DFT by directly implementing the definition of the DFT sum from Eq. and takes N² seconds to run. Program B implements the decimation-in-time FFT algorithm and takes 10N log₂ N seconds to run. What is the shortest sequence N such that program B turns faster than program A?

Transcribed Image Text:

N-1 Analysis equation: X[k] = *[n]w". (8.67) %3D