next up previous
Next: 4.2 Conclusion Up: 4 Discussion Previous: 4 Discussion

4.1 Time complexity and scalability analysis

The DFT (see Section 2.2) of an array of \( n \) elements can be computed in \( \Theta (n\lg n) \) time10 using the Fast Fourier Transform (FFT) method as derived in [Cormen et al, 1997, Sections 32.2 and 32.3] and as employed by FFTW. To (point-wise) multiply or divide two arrays each of size \( n \) together requires \( \Theta (n) \) time. Thus each of the convolutions takes \( \Theta (n) \) time in Fourier space, and \( \Theta (n\lg n) \) time to transform between Euclidean and Fourier space. To perform the smoothing requires a constant amount of time (e.g. 8 elements or 24 elements for a 3x3 or 5x5 matrix respectively) for each pixel, thus this step also requires \( \Theta (n) \) time. This is similar to the weighting step, which considers 8 neighbours, thus also having time complexity \( \Theta (n) \). Therefore our entire algorithm has time complexity of \( \Theta (n\lg n) \), which scales well11 as \( n\rightarrow \infty \).

Kevin Pulo