Area-time complexity for VLSI
Clark D. Thompson · 1979
The complexity of the Discrete Fourier Transform (DFT) is studied with respect to a new model of computation appropriate to VLSI technology. This model focuses on two key parameters, the amount of silicon area and time required to implement a DFT on a single chip. Lower bounds on area (A) and time (T) are related to the number of points (N) in the DFT: AT2≥ N2/16. This inequality holds for any chip design based on any algorithm, and is nearly tight when T = θ(N1/2) or T = θ(log N). A more general lower bound is also derived: ATx = Ω(N1+x/2), for 0≤×≤2.