Spectrogram visualization in Signal Processing - Time & Space Complexity

Time Complexity: Spectrogram visualization

O(n log n)

Understanding Time Complexity

When creating a spectrogram, we want to know how the time to process the signal changes as the signal gets longer.

We ask: How does the work grow when the input signal size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.signal import spectrogram

def compute_spectrogram(signal, fs, nperseg):
    f, t, Sxx = spectrogram(signal, fs=fs, nperseg=nperseg)
    return f, t, Sxx

# signal: input array of length N
# fs: sampling frequency
# nperseg: segment length

This code computes the spectrogram by splitting the signal into segments and applying FFT to each segment.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Computing FFT on each segment of the signal.
• How many times: Number of segments, which depends on signal length divided by segment size.

How Execution Grows With Input

As the signal length grows, the number of segments grows roughly in proportion.

Input Size (n)	Approx. Operations
10,000	About 10,000 / nperseg FFT computations
100,000	About 100,000 / nperseg FFT computations
1,000,000	About 1,000,000 / nperseg FFT computations

Pattern observation: Doubling the input roughly doubles the number of FFT computations, so work grows linearly with input size.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than linearly because each FFT takes time proportional to segment size times log of segment size, and we do many segments.

Common Mistake

[X] Wrong: "The spectrogram computation time grows only linearly with input size because it just splits the signal."

[OK] Correct: Each segment requires an FFT, which itself takes more than linear time (it takes n log n time for segment size n), so total time is more than just linear.

Interview Connect

Understanding how spectrogram computation scales helps you explain performance in real signal analysis tasks, showing you grasp both algorithm steps and their costs.

Self-Check

"What if we change the segment length to be very small or very large? How would that affect the time complexity?"

Practice

1. What does a spectrogram primarily show in signal processing?

easy

A. How signal frequencies change over time

B. The total energy of a signal

C. The raw amplitude values of a signal

D. The phase shift of a signal

Solution

1. Step 1: Understand spectrogram purpose

   A spectrogram is a visual tool that shows frequency content of a signal as it changes over time.

2. Step 2: Compare options to definition

   Only How signal frequencies change over time describes frequency changes over time, which matches the spectrogram's function.

3. Final Answer:

   How signal frequencies change over time -> Option A

4. Quick Check:

   Spectrogram = frequency over time [OK]

Hint: Spectrogram = frequency vs time graph [OK]

Common Mistakes:

• Confusing spectrogram with waveform plot
• Thinking it shows only amplitude
• Mixing phase information with frequency

2. Which Python library is commonly used to create spectrograms?

easy

A. matplotlib

B. pandas

C. scikit-learn

D. numpy

Solution

1. Step 1: Identify libraries for plotting

   matplotlib is widely used for plotting graphs including spectrograms.

2. Step 2: Check other libraries' main uses

   pandas is for data frames, scikit-learn for machine learning, numpy for arrays but not direct plotting.

3. Final Answer:

   matplotlib -> Option A

4. Quick Check:

   Plotting spectrogram = matplotlib [OK]

Hint: Plotting graphs? Think matplotlib [OK]

Common Mistakes:

• Choosing numpy for plotting directly
• Confusing pandas with plotting library
• Selecting scikit-learn which is for ML

3. Given this Python code snippet, what is the shape of the output spectrogram array?

import numpy as np
from scipy.signal import spectrogram

fs = 1280  # Sampling frequency
x = np.sin(2 * np.pi * 50 * np.linspace(0, 1, fs))
f, t, Sxx = spectrogram(x, fs)
print(Sxx.shape)

medium

A. (1000, 1000)

B. (129, 9)

C. (50, 1000)

D. (1000, 129)

Solution

1. Step 1: Understand spectrogram output dimensions

   The spectrogram function returns frequency bins and time bins. For default parameters, frequency bins are nfft/2+1 (default nfft=256), so 129 frequency bins.

2. Step 2: Calculate time bins

   With 1 second signal sampled at 1280 Hz and default windowing, time bins are 9 segments.

3. Final Answer:

   (129, 9) -> Option B

4. Quick Check:

   Frequency bins = 129, Time bins = 9 [OK]

Hint: Spectrogram shape = (freq_bins, time_bins) [OK]

Common Mistakes:

• Assuming output shape matches input length
• Confusing frequency bins with sampling rate
• Mixing up rows and columns in output

4. Identify the error in this code snippet for plotting a spectrogram:

import matplotlib.pyplot as plt
from scipy.signal import spectrogram

fs = 500
x = [1, 2, 3, 4, 5]
f, t, Sxx = spectrogram(x, fs)
plt.specgram(Sxx)
plt.show()

medium

A. Using plt.specgram instead of plt.plot

B. Missing import for numpy

C. Sampling frequency fs is too high

D. Passing Sxx instead of x to plt.specgram

Solution

1. Step 1: Understand spectrogram output and plotting

   The spectrogram function returns frequencies, times, and the spectrogram matrix Sxx. plt.specgram expects raw signal, not Sxx.

2. Step 2: Identify misuse of plt.specgram

   Passing Sxx (already spectrogram data) to plt.specgram causes error; should plot Sxx with plt.imshow or pass raw signal to plt.specgram.

3. Final Answer:

   Passing Sxx instead of x to plt.specgram -> Option D

4. Quick Check:

   Plot raw signal with plt.specgram, not spectrogram matrix [OK]

Hint: plt.specgram needs raw signal, not spectrogram data [OK]

Common Mistakes:

• Passing spectrogram matrix to plt.specgram
• Confusing plt.specgram with plt.imshow
• Ignoring correct input types for plotting

5. You want a spectrogram with smoother frequency resolution but less time detail. Which parameter should you increase?

hard

A. Sampling frequency (fs)

B. Overlap between windows (noverlap)

C. Window size (nperseg)

D. FFT length (nfft) smaller than window size

Solution

1. Step 1: Understand window size effect on spectrogram

   Larger window size increases frequency resolution but reduces time resolution (smoother frequency, less time detail).

2. Step 2: Evaluate other parameters

   Increasing overlap smooths time axis but does not improve frequency resolution as much. Sampling frequency affects max frequency, not resolution. nfft smaller than window size is invalid.

3. Final Answer:

   Window size (nperseg) -> Option C

4. Quick Check:

   Increase window size for better frequency resolution [OK]

Hint: Bigger window = better frequency, worse time detail [OK]

Common Mistakes:

• Increasing overlap to improve frequency resolution
• Changing sampling frequency to affect resolution
• Setting nfft smaller than window size