That complexity bound applies to polynomials over more general coefficient rings which may not have roots of unity. Over the usual complex numbers the complexity is O(n log n).
The (log (log n)) factor in asymptotic complexity notation is almost meaningless.
* log₂ log₂ 2⁶⁴ = 6, which is essentially a constant factor if N<2⁶⁴
* to be fair, you may need to consider (log log N), or even (log log N)² factors hidden in native computer word size if exceeding N = 2⁶⁴.
* Today's machines have gone far from the classical computational complexity models, where data access patterns and locality matter orders of magnitude more than a factor which is essentially <= 6.
I would not immediately discard a (log log n) factor, but for nearly all purposes, I would mostly disregard it. So if the only difference were O(n·log n) vs O(n·log n·log log n), then no, it would not be a big deal.
Let us now focus on the computation of the inverse chirp transform. The idea is to use the Newton basis for intermediate computations: first perform a Newton interpolation, then perform a conversion from the Newton basis to the monomial basis. Both steps have complexities M(n) + O(n), which gives the estimate of 2M(n) + O(n)
The function M(n)
denotes the cost of multiplying univariate polynomials of degree less than n. Using FFT-based multiplication algorithms, M(n) can be taken in O(n log(n) log(log(n)))
So they did not reach O(n log n).