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