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.