[Lichtso]

O(n log n) for the x axis (time samples) and O(n) for the y axis (frequencies).

But you can downsample the signal in frequency domain, meaning you will pay mostly for the output resolution.