Frequency spectrum interpretation in Signal Processing - Time & Space Complexity

Time Complexity: Frequency spectrum interpretation

O(n log n)

Understanding Time Complexity

We want to understand how the time to analyze a signal's frequency spectrum changes as the signal length grows.

How does the work needed to get frequency details increase when the input signal gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

def compute_spectrum(signal):
    n = len(signal)
    spectrum = np.fft.fft(signal)
    magnitude = np.abs(spectrum)
    return magnitude
    

This code computes the frequency spectrum magnitude of a signal using the Fast Fourier Transform (FFT).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The FFT algorithm processes the entire signal array.
• How many times: It performs operations proportional to the signal length times the logarithm of the signal length.

How Execution Grows With Input

As the signal length grows, the work grows a bit faster than just the length itself but much slower than the square of the length.

Input Size (n)	Approx. Operations
10	About 33 operations
100	About 664 operations
1000	About 9966 operations

Pattern observation: The operations grow faster than the input size but much slower than if we did every pair of points.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to compute the frequency spectrum grows a bit faster than the signal length but stays efficient even for large signals.

Common Mistake

[X] Wrong: "Computing the frequency spectrum takes time proportional to the square of the signal length because it compares every point to every other point."

[OK] Correct: The FFT algorithm cleverly reduces the work by breaking the problem into smaller parts, so it only grows like n times log n, not n squared.

Interview Connect

Understanding how FFT scales helps you explain why it is widely used in signal processing and data analysis, showing your grasp of efficient algorithms.

Self-Check

"What if we replaced FFT with a simple discrete Fourier transform (DFT) that uses nested loops? How would the time complexity change?"

Practice

1. What does a peak in a frequency spectrum represent in signal processing?

easy

A. A strong presence of a specific frequency in the signal

B. The time duration of the signal

C. The amplitude of the original time signal

D. The noise level in the signal

Solution

1. Step 1: Understand frequency spectrum meaning

   The frequency spectrum shows how much of each frequency is present in the signal.

2. Step 2: Interpret peaks in the spectrum

   A peak means that frequency has a strong presence or high amplitude in the signal.

3. Final Answer:

   A strong presence of a specific frequency in the signal -> Option A

4. Quick Check:

   Peak = strong frequency presence [OK]

Hint: Peaks show strong frequencies in the signal [OK]

Common Mistakes:

• Confusing time duration with frequency
• Thinking amplitude in time domain equals peak in spectrum
• Assuming noise causes peaks

2. Which of the following is the correct way to compute the frequency spectrum of a signal in Python using numpy?

easy

A. np.fft.freq(signal)

B. np.fft.ifft(signal)

C. np.fft.fft(signal)

D. np.fft.spectrum(signal)

Solution

1. Step 1: Recall numpy FFT functions

   np.fft.fft() computes the Fourier Transform to get frequency spectrum.

2. Step 2: Check other options

   np.fft.ifft() computes inverse FFT, others do not exist.

3. Final Answer:

   np.fft.fft(signal) -> Option C

4. Quick Check:

   FFT = np.fft.fft() [OK]

Hint: Use np.fft.fft() for frequency spectrum [OK]

Common Mistakes:

• Using inverse FFT instead of FFT
• Using non-existent numpy functions
• Confusing frequency and time domain functions

3. Given the Python code:

import numpy as np
signal = np.sin(2 * np.pi * 5 * np.linspace(0, 1, 100))
spectrum = np.fft.fft(signal)
peak_freq_index = np.argmax(np.abs(spectrum))
print(peak_freq_index)

What is the printed output?

medium

A. 50

B. 95

C. 0

D. 5

Solution

1. Step 1: Understand the signal frequency

   The signal is a sine wave at 5 Hz sampled 100 times over 1 second.

2. Step 2: Find peak frequency index in FFT

   FFT peak index corresponds to frequency 5, so index 5 is max magnitude.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Peak index = frequency = 5 [OK]

Hint: Peak index matches sine wave frequency [OK]

Common Mistakes:

• Confusing index with frequency value
• Ignoring sampling rate and length
• Mistaking negative frequency indices

4. The following code attempts to find the main frequency in a signal but gives wrong results:

import numpy as np
signal = np.sin(2 * np.pi * 10 * np.linspace(0, 1, 100))
spectrum = np.fft.fft(signal)
peak = np.argmax(spectrum)
print(peak)

What is the error?

medium

A. Using np.fft.fft instead of np.fft.ifft

B. Using np.argmax on complex spectrum instead of magnitude

C. Signal frequency is too high for sampling rate

D. Not normalizing the spectrum before argmax

Solution

1. Step 1: Check how peak is found

   np.argmax(spectrum) finds max of complex numbers, which is incorrect.

2. Step 2: Correct method to find peak

   Use np.argmax(np.abs(spectrum)) to find peak magnitude index.

3. Final Answer:

   Using np.argmax on complex spectrum instead of magnitude -> Option B

4. Quick Check:

   Peak must be on magnitude, not complex values [OK]

Hint: Use magnitude (abs) before argmax [OK]

Common Mistakes:

• Argmax on complex array directly
• Confusing FFT and IFFT
• Ignoring magnitude for peak detection

5. You have a signal composed of two sine waves at 3 Hz and 7 Hz sampled at 50 Hz for 2 seconds. Which code snippet correctly identifies both frequencies from the frequency spectrum?

hard

A. import numpy as np
t = np.linspace(0, 2, 100)
signal = np.sin(2*np.pi*3*t) + np.sin(2*np.pi*7*t)
spectrum = np.fft.fft(signal)
freqs = np.fft.fftfreq(len(t), d=1/50)
peaks = freqs[np.argsort(np.abs(spectrum))[-2:]]
print(np.sort(np.abs(peaks)))

B. import numpy as np
t = np.linspace(0, 2, 100)
signal = np.sin(2*np.pi*3*t) + np.sin(2*np.pi*7*t)
spectrum = np.fft.ifft(signal)
freqs = np.fft.fftfreq(len(t), d=1/50)
peaks = freqs[np.argmax(np.abs(spectrum))]
print(peaks)

C. import numpy as np
t = np.linspace(0, 2, 50)
signal = np.sin(2*np.pi*3*t) + np.sin(2*np.pi*7*t)
spectrum = np.fft.fft(signal)
freqs = np.fft.fftfreq(len(t), d=1/50)
peaks = freqs[np.argsort(np.abs(spectrum))[-2:]]
print(np.sort(np.abs(peaks)))

D. import numpy as np
t = np.linspace(0, 2, 100)
signal = np.sin(2*np.pi*3*t) + np.sin(2*np.pi*7*t)
spectrum = np.fft.fft(signal)
freqs = np.fft.fftfreq(len(t), d=1/100)
peaks = freqs[np.argsort(np.abs(spectrum))[-2:]]
print(np.sort(np.abs(peaks)))

Solution

1. Step 1: Check sampling and signal length

   Sampling at 50 Hz for 2 seconds means 100 samples, so t has 100 points.

2. Step 2: Verify FFT and frequency calculation

   Use np.fft.fft(signal) and np.fft.fftfreq with d=1/50 for correct frequency bins.

3. Step 3: Identify two largest peaks

   Sort magnitudes and pick last two indices for peaks, then print sorted absolute frequencies.

4. Final Answer:

   Code snippet D correctly identifies both frequencies -> Option A

5. Quick Check:

   Correct sampling, FFT, freq bins, and peak selection [OK]

Hint: Match sample count and rate, use fftfreq with correct d [OK]

Common Mistakes:

• Using inverse FFT instead of FFT
• Wrong sample count or sampling interval
• Incorrect frequency bin calculation