Real FFT (rfft) in SciPy - Time & Space Complexity

Time Complexity: Real FFT (rfft)

O(n log n)

Understanding Time Complexity

We want to understand how the time it takes to compute a real FFT changes as the input size grows.

How does the work needed grow when we give the function longer signals?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.fft import rfft

signal = np.random.rand(1024)  # real input signal
fft_result = rfft(signal)
    

This code computes the real FFT of a signal with 1024 points, transforming it into frequency components.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The FFT algorithm repeatedly combines and processes pairs of data points through stages.
• How many times: The number of stages grows roughly with the logarithm of the input size.

How Execution Grows With Input

As the input size doubles, the number of operations grows a bit more than double but much less than square.

Input Size (n)	Approx. Operations
10	About 30
100	About 700
1000	About 10,000

Pattern observation: The operations grow roughly like n times log n, which is faster than just n but slower than n squared.

Final Time Complexity

Time Complexity: O(n log n)

This means if you double the input size, the work grows a bit more than twice, but not as much as four times.

Common Mistake

[X] Wrong: "The FFT runs in linear time, so doubling input size doubles the time exactly."

[OK] Correct: FFT uses a divide-and-conquer approach, so the time grows a bit faster than linear, because it processes multiple stages.

Interview Connect

Understanding FFT time complexity helps you explain how signal processing scales and shows you can analyze efficient algorithms.

Self-Check

"What if we used a standard FFT on complex input instead of rfft on real input? How would the time complexity change?"