Complexity of computing the discrete Fourier transform?
This answer is a variant of the analysis of the first algorithm
("Methode A") by Schönhage and Strassen for multiplication of long integers.

Assume we want to compute an FFT of length $K = 2^k$.
Scale your input such that all values are smaller than 1. 
Let us first assume that we compute with $m$-bit fixed point arithmetic
($m$ bits after the binary point). Let $\delta = 2^{1/2 -m}$ be the 
("complex") unit of least position. Let $\omega =  \exp(2\pi i/K)$.

1) One can compute approximations $\omega_j&#39;$ such that
$|\omega_j&#39; - \omega^j| \le (2k-1)\delta$ for all $0 \le j \le K-1$.
This can be done in time $O(K M(m))$ where $M(m)$ is the time needed
to multiply $m$-bit numbers. (see Knuth Vol. 2, 3rd ed., page 309).

If standard integer RAM means logarithmic cost, then $M(m) = O(m \log m)$.
If standard integer RAM means word RAM, then $M(m) = O(m)$. (Schönhage and Strassen show in "Methode A" how to reduce in linear time the multiplication of $m$-bit numbers to $m$ multiplication of $O(\log m)$ bit numbers. The latter can be done at unit costs.) 

2) The classical Cooley-Tukey FFT computes operations of the form
$a = b + \omega^j c$. We use $m$-bit fixed point arithmetic,
these opertions become $a&#39; = truncate(b&#39; + \omega_j&#39; c&#39;)$.
If we know $b&#39;$ and $c&#39;$ up to an error of $\epsilon$, we get $a&#39;$ up to an error of $2\epsilon + 2k\delta$.

3) Using induction, it is easy to see that we get the final result
with error $(2^k - 1) \cdot 2k\delta$. To get precision $b$ in the end,
$m \ge k + \log k + b + O(1)$.  

4) Thus the final running time is $O(K k M(k+b))$.

This should also work with floating point numbers: 1) can still be done with fixed point arithmetic, 2) is also true for floating point numbers.



In fixed point arithmetic, I think, it can even be done faster. 
First we reduce the computation of the FFT to the multiplication of 
polynomials using Bluestein's trick. 
The length of the coefficients needed to get the desired precision
should be $O(k + b)$.
Then we reduce the multiplication of polynomials to the multiplication
of long integers. (Append the coefficients to a long number and separate them by blocks of zero of length $O(k+b)$.) The length of the integers is $O(K(k+b))$.