Here's one: the FFT Algorithm allows transformation between positional space and fourier space (for a 1d signal, like audio, this is the transformation between a "time" based and a "frequency" based signal) and vice-versa in O(n * lg n) time for n power of 2.
Why is this important? Convolution, the primary operation involved in computing all kinds of neat filters, can be performed in O(n^2) time in time space, but O(n) time in frequency space. (i.e. it's a lot faster to perform image filtering in Fourier space). The problem is that the normal Fourier transform takes O(n^2) time, so you can't get into and out of Fourier space to justify performing filtering there.
With the FFT, filtering can be performed in O(n*lg n) time, since you can hop into Fourier space quickly, perform the filter, and hop back (the constants work out to this being useful after n ~= 100,000, which is a reasonable point for audio and most images).
The FFT is a great example of an algorithm that suddenly tipped the asymptotic scales and revolutionized an entire discipline.
Re:Translation (Score:4)
Why is this important? Convolution, the primary operation involved in computing all kinds of neat filters, can be performed in O(n^2) time in time space, but O(n) time in frequency space. (i.e. it's a lot faster to perform image filtering in Fourier space). The problem is that the normal Fourier transform takes O(n^2) time, so you can't get into and out of Fourier space to justify performing filtering there.
With the FFT, filtering can be performed in O(n*lg n) time, since you can hop into Fourier space quickly, perform the filter, and hop back (the constants work out to this being useful after n ~= 100,000, which is a reasonable point for audio and most images).
The FFT is a great example of an algorithm that suddenly tipped the asymptotic scales and revolutionized an entire discipline.
-m