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).