FFT is O(n log n), not O(n). The better O(n) algorithms are the likes of Deriche...

		anderskaseorg 6 days ago \| parent \| context \| favorite \| on: C vs. C#: racing VLC's Gaussian blur FFT is O(n log n), not O(n). The better O(n) algorithms are the likes of Deriche, Vliet–Young–Verbeek, or Alvarez–Mazorra.
		help