Short-Time Fourier Transform (STFT) in Signal Processing - Time & Space Complexity

Time Complexity: Short-Time Fourier Transform (STFT)

O(n log m)

Understanding Time Complexity

We want to understand how the time it takes to compute the Short-Time Fourier Transform changes as the input signal gets longer.

How does the work grow when we analyze more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.signal import stft

# x is the input signal array
# fs is the sampling frequency
f, t, Zxx = stft(x, fs=fs, nperseg=window_size, noverlap=overlap)

This code splits the signal into overlapping windows and computes the Fourier transform on each window.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Computing the Fourier transform on each window segment.
• How many times: Once for each window, which depends on the signal length and window step size.

How Execution Grows With Input

As the input signal length grows, the number of windows increases roughly in proportion to the signal length.

Input Size (n)	Approx. Operations
10,000 samples	About 10,000 / (window_size - overlap) Fourier transforms
100,000 samples	About 10 times more Fourier transforms than 10,000 samples
1,000,000 samples	About 100 times more Fourier transforms than 10,000 samples

Pattern observation: The total work grows roughly linearly with the input size.

Final Time Complexity

Time Complexity: O(n \log m)

This means the time grows roughly proportional to the input length times the cost of each Fourier transform on a window of size m.

Common Mistake

[X] Wrong: "The STFT time grows only with the number of windows, ignoring the cost of each Fourier transform."

[OK] Correct: Each window requires a Fourier transform, which itself takes time proportional to the window size times a logarithm factor, so ignoring this underestimates the total time.

Interview Connect

Understanding how STFT scales helps you explain performance in real signal analysis tasks, showing you can think about both data size and algorithm steps clearly.

Self-Check

"What if we doubled the window size while keeping the signal length the same? How would the time complexity change?"