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?"

Practice

1. What does the scipy.fft.rfft function compute when applied to a real-valued signal?

easy

A. The full complex Fourier transform including negative frequencies

B. The positive frequency components of the signal's Fourier transform

C. The inverse Fourier transform of the signal

D. The time-domain signal filtered by a low-pass filter

Solution

1. Step 1: Understand the input type

   rfft is designed for real-valued input signals.

2. Step 2: Analyze the output of rfft

   It returns only the positive frequency components because the negative frequencies are mirror images for real signals.

3. Final Answer:

   The positive frequency components of the signal's Fourier transform -> Option B

4. Quick Check:

   Real input -> half spectrum output [OK]

Hint: Real signals -> use rfft for positive frequencies only [OK]

Common Mistakes:

• Confusing rfft with full fft output
• Thinking rfft returns time-domain data
• Assuming rfft returns negative frequencies

2. Which of the following is the correct way to import and use rfft from SciPy's FFT module?

easy

A. import scipy.fft as rfft
result = rfft.rfft(signal)

B. import scipy.rfft
result = scipy.rfft(signal)

C. from scipy.fft import rfft
result = rfft(signal)

D. from scipy import rfft
result = rfft.fft(signal)

Solution

1. Step 1: Recall correct import syntax

   The rfft function is in scipy.fft, so import it directly from there.

2. Step 2: Check usage

   Calling rfft(signal) after import is the correct usage.

3. Final Answer:

   from scipy.fft import rfft\nresult = rfft(signal) -> Option C

4. Quick Check:

   Correct import and call syntax [OK]

Hint: Import rfft directly from scipy.fft for simple use [OK]

Common Mistakes:

• Trying to import rfft from scipy directly
• Using wrong module names
• Calling rfft as a method of scipy.fft without import

3. What is the output of the following code?

import numpy as np
from scipy.fft import rfft
signal = np.array([1, 0, -1, 0])
result = rfft(signal)
print(np.round(result, 2))

medium

A. [0.+0.j 1.+0.j 0.+0.j]

B. [0.+0.j 0.+0.j 0.+0.j]

C. [0.+0.j -2.+0.j 0.+0.j]

D. [0.+0.j 2.+0.j 0.+0.j]

Solution

1. Step 1: Understand the input signal

   The signal is [1, 0, -1, 0], a simple 4-point real array.

2. Step 2: Compute rfft manually or recall pattern

   rfft returns N/2+1 = 3 complex values for length 4 input. The values correspond to DC, positive frequency, and Nyquist frequency components. The result is approximately [0.+0.j, 2.+0.j, 0.+0.j].

3. Final Answer:

   [0.+0.j 2.+0.j 0.+0.j] -> Option D

4. Quick Check:

   rfft length 4 -> 3 outputs, middle value 2 [OK]

Hint: rfft output length = input//2 + 1 [OK]

Common Mistakes:

• Expecting output length same as input
• Ignoring complex number format
• Misreading the signal values

4. Identify the error in this code snippet using rfft and fix it:

import numpy as np
from scipy.fft import rfft
signal = [1, 2, 3, 4]
result = rfft(signal, n=2)
print(result)

medium

A. The parameter n is smaller than signal length; use n=4 instead

B. The input signal must be a NumPy array, not a list

C. rfft does not accept the parameter n

D. The import statement is incorrect; use import scipy.fftpack

Solution

1. Step 1: Check the n parameter usage

   The n parameter sets the length of the FFT. Here, n=2 is less than the signal length 4, so the signal is truncated.

2. Step 2: Fix the parameter to match or exceed signal length

   Using n=4 ensures the full signal is transformed without truncation.

3. Final Answer:

   The parameter n is smaller than signal length; use n=4 instead -> Option A

4. Quick Check:

   FFT length must cover signal length [OK]

Hint: Set n ≥ signal length to avoid truncation [OK]

Common Mistakes:

• Passing list instead of array (allowed but less efficient)
• Ignoring effect of n parameter truncation
• Wrong import module for rfft

5. You have a real sensor signal sampled at 100 Hz with 1000 points. You want to find the frequency with the highest amplitude using rfft. Which code snippet correctly computes this frequency?

hard

A. import numpy as np
from scipy.fft import rfft, rfftfreq
signal = np.random.rand(1000)
fft_vals = rfft(signal)
freqs = rfftfreq(len(signal), 1/100)
peak_freq = freqs[np.argmax(np.abs(fft_vals))]
print(peak_freq)

B. import numpy as np
from scipy.fft import fft
signal = np.random.rand(1000)
fft_vals = fft(signal)
freqs = np.fft.fftfreq(len(signal), 1/100)
peak_freq = freqs[np.argmax(np.abs(fft_vals))]
print(peak_freq)

C. import numpy as np
from scipy.fft import rfft
signal = np.random.rand(1000)
fft_vals = rfft(signal)
peak_freq = np.argmax(np.abs(fft_vals))
print(peak_freq)

D. import numpy as np
from scipy.fft import rfft, rfftfreq
signal = np.random.rand(1000)
fft_vals = rfft(signal)
freqs = rfftfreq(len(signal), 100)
peak_freq = freqs[np.argmax(np.abs(fft_vals))]
print(peak_freq)

Solution

1. Step 1: Use rfft and rfftfreq correctly

   For real signals, rfft computes the positive frequencies, and rfftfreq gives the corresponding frequency bins. The sampling interval is 1/100 seconds.

2. Step 2: Find the peak frequency

   Calculate the absolute values of FFT coefficients, find the index of the max, then map to frequency using freqs.

3. Final Answer:

   Code snippet A correctly computes the peak frequency -> Option A

4. Quick Check:

   Use rfft + rfftfreq with correct sampling interval [OK]

Hint: Use rfftfreq with 1/sampling_rate for correct frequencies [OK]

Common Mistakes:

• Using fft and fftfreq for real signals (less efficient)
• Wrong sampling interval in rfftfreq
• Not mapping peak index to frequency