CuFFT Complexity Class

Does anyone have any idea or documentation as to the Big O complexity class for CuFFT. So far all I’ve been able to find is a single line in a research paper that reported O(n^2). That doesn’t seem quite right to me. Any info or references are greatly appreciated.