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 mos

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.