Coordinate transformations computational considerations

A straightforward implementation of the Fourier transform requires O (N2) operations, where n = nx x ny is the number of pixels of the input image. A number of optimizations can be applied to reduce the time needed to perform this transformation. First, the transformation is separable. Therefore, the transformation can be performed independently for the two coordinates. Second, if the image dimensions are a power of two then the Fourier transformation can be computed recursively, which gives a considerable speedup. This is known... 

---