Windowing before FFT in SciPy - Time & Space Complexity

Time Complexity: Windowing before FFT

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to apply a window and then compute an FFT changes as the input size grows.

How does the work increase when we have more data points?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.signal import windows
from scipy.fft import fft

n = 1024
signal = np.random.rand(n)
window = windows.hann(n)
windowed_signal = signal * window
fft_result = fft(windowed_signal)

This code creates a window, applies it to a signal, and then computes the FFT of the windowed signal.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying each element of the signal by the window (element-wise multiplication) and computing the FFT.
• How many times: Both operations process all n elements once; FFT internally performs about n log n steps.

How Execution Grows With Input

As the input size n grows, the windowing step grows linearly, but the FFT grows a bit faster.

Input Size (n)	Approx. Operations
10	~10 (window) + ~33 (FFT)
100	~100 (window) + ~664 (FFT)
1000	~1000 (window) + ~9966 (FFT)

Pattern observation: The windowing grows straight with n, but FFT grows a bit faster, roughly n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the total time grows a bit faster than just the number of data points, mainly because of the FFT step.

Common Mistake

[X] Wrong: "The windowing step dominates the time because it touches every data point."

[OK] Correct: While windowing is linear, the FFT step is more complex and grows faster, so it dominates the total time as input size grows.

Interview Connect

Understanding how windowing and FFT scale helps you explain performance in signal processing tasks clearly and confidently.

Self-Check

"What if we replaced the FFT with a slower, direct DFT calculation? How would the time complexity change?"