4.1 Time complexity and scalability analysis

The DFT (see Section 2.2) of an array of elements can be computed in time¹⁰ 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 together requires time. Thus each of the convolutions takes time in Fourier space, and 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 time. This is similar to the weighting step, which considers 8 neighbours, thus also having time complexity . Therefore our entire algorithm has time complexity of , which scales well¹¹ as .