FFT-based filtering in SciPy - Time & Space Complexity

Time Complexity: FFT-based filtering

O(n log n)

Understanding Time Complexity

When using FFT-based filtering, we want to know how the time to process data changes as the data size grows.

We ask: How does the filtering time increase when the input signal gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.fft import fft, ifft

def fft_filter(signal, filter_kernel):
    n = len(signal) + len(filter_kernel) - 1
    signal_fft = fft(signal, n)
    filter_fft = fft(filter_kernel, n)
    filtered_fft = signal_fft * filter_fft
    filtered_signal = ifft(filtered_fft)
    return np.real(filtered_signal)

This code filters a signal by transforming both the signal and filter to frequency space, multiplying them, and then transforming back.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The FFT and inverse FFT computations, which internally perform repeated calculations over the input arrays.
• How many times: Each FFT processes an array of size approximately n (sum of input lengths), doing about n log n steps.

How Execution Grows With Input

As the input size n grows, the number of operations grows a bit faster than n but much slower than n squared.

Input Size (n)	Approx. Operations
10	About 10 x log₂(10) ≈ 33
100	About 100 x log₂(100) ≈ 664
1000	About 1000 x log₂(1000) ≈ 9966

Pattern observation: Operations grow faster than the input size but much slower than if we did every pairwise multiplication.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to filter grows a bit faster than the input size but remains efficient even for large inputs.

Common Mistake

[X] Wrong: "FFT-based filtering takes time proportional to n squared because it multiplies all pairs of points."

[OK] Correct: FFT uses a clever method to reduce repeated calculations, so it runs much faster than checking every pair.

Interview Connect

Understanding FFT time complexity shows you can analyze efficient algorithms that handle large data quickly, a useful skill in many data science tasks.

Self-Check

"What if we used a direct convolution instead of FFT-based filtering? How would the time complexity change?"