Given a known function $f$, I am wondering how fast (depending on $n$) we can numerically approximate the Fourier coefficients $\int_0^1 f(x) e^{2\pi i n x} \, \mathrm{d}x$, either for fixed $n$ or for all $n$ between some bounds $-N$ and $N$. In particular, if there are any tricks (like the FFT) here that would make this faster than an ordinary integration problem.
In particular, can $\int_0^1 f(x) e^{2\pi i n x} \, \mathrm{d}x$ be approximated reasonably well in constant difficulty $\mathcal{O}(1)$ in $n$? Or at least in $\mathcal{O}(n)$?