** 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 elements
can be computed in
time^{10} 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^{11} as
.

*Kevin Pulo*

2000-08-22