Spectrograms in MATLAB - Time & Space Complexity

Time Complexity: Spectrograms

O(n log m)

Understanding Time Complexity

When creating spectrograms, we want to know how the time to compute grows as the input signal gets longer.

We ask: How does the processing time change when the audio or signal length increases?

Scenario Under Consideration

Analyze the time complexity of the following MATLAB code snippet.

fs = 8000; % Sampling frequency
x = randn(1, n); % Input signal of length n
window = hamming(256);
overlap = 128;
[S, F, T] = spectrogram(x, window, overlap, 512, fs);
    

This code computes the spectrogram of a signal x using a sliding window and overlap.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Computing the Fast Fourier Transform (FFT) for each window segment.
• How many times: The number of windows is roughly proportional to the signal length divided by the hop size (window length minus overlap).

How Execution Grows With Input

As the input signal length grows, the number of windows increases linearly, so the total FFT computations grow linearly too.

Input Size (n)	Approx. Operations
10,000	About 80 FFTs
100,000	About 800 FFTs
1,000,000	About 8,000 FFTs

Pattern observation: Doubling the input roughly doubles the number of FFT computations.

Final Time Complexity

Time Complexity: O(n log m)

This means the time grows roughly proportional to the input length times the logarithm of the FFT size.

Common Mistake

[X] Wrong: "The spectrogram computation time grows only with the input length n, ignoring the FFT cost per window."

[OK] Correct: Each window requires an FFT, which takes time proportional to the FFT size times its logarithm, so the FFT size matters too.

Interview Connect

Understanding how spectrogram computation scales helps you explain performance in signal processing tasks clearly and confidently.

Self-Check

"What if we changed the window size to be twice as large? How would the time complexity change?"

Practice

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

easy

A. The total energy of a signal

B. How frequencies change over time in a signal

C. The amplitude of a signal at a single point

D. The phase shift of a signal

Solution

1. Step 1: Understand the purpose of a spectrogram

   A spectrogram is a visual tool that shows how the frequency content of a signal varies over time.

2. Step 2: Compare options with the definition

   Only How frequencies change over time in a signal correctly describes this as frequency changes over time, while others describe different signal properties.

3. Final Answer:

   How frequencies change over time in a signal -> Option B

4. Quick Check:

   Spectrogram = frequency vs time [OK]

Hint: Spectrogram = frequency changes over time [OK]

Common Mistakes:

• Confusing amplitude with frequency
• Thinking spectrogram shows total energy
• Mixing phase shift with frequency content

2. Which of the following is the correct syntax to create a spectrogram in MATLAB for signal x with window size 256 and overlap 128?

easy

A. spectrogram(x,256,128)

B. spectrogram(x,128,256)

C. spectrogram(256,x,128)

D. spectrogram(x,128)

Solution

1. Step 1: Recall MATLAB spectrogram syntax

   The syntax is spectrogram(signal,window,overlap), so the window size comes before overlap.

2. Step 2: Match parameters to syntax

   spectrogram(x,256,128) correctly uses spectrogram(x,256,128) where 256 is window size and 128 is overlap.

3. Final Answer:

   spectrogram(x,256,128) -> Option A

4. Quick Check:

   Correct order: signal, window, overlap [OK]

Hint: Remember: spectrogram(signal, window, overlap) [OK]

Common Mistakes:

• Swapping window and overlap values
• Passing window size as first argument
• Omitting required parameters

3. What will be the output size of the matrix S when running [S,F,T] = spectrogram(x,128,64,256,1000); if x is a 1-second signal sampled at 1000 Hz?

medium

A. 256 rows by 15 columns

B. 128 rows by 16 columns

C. 129 rows by 14 columns

D. 129 rows by 16 columns

Solution

1. Step 1: Calculate frequency bins (rows)

   Frequency bins = nfft/2 + 1 = 256/2 + 1 = 129 rows.

2. Step 2: Calculate time bins (columns)

   Signal length = 1000 samples, window=128, overlap=64, step = 128-64=64 samples.
   Number of segments = floor((1000-128)/64) + 1 = floor(872/64) + 1 = 13 + 1 = 14 columns.

3. Final Answer:

   129 rows by 14 columns -> Option C

4. Quick Check:

   Rows = 129, Columns = 14 [OK]

Hint: Rows = nfft/2+1, columns depend on window and overlap [OK]

Common Mistakes:

• Confusing nfft with window size for rows
• Miscounting number of segments
• Ignoring overlap in time bins calculation

4. Given the code snippet:

x = randn(1,1000);
[S,F,T] = spectrogram(x,256,128,512,1000);
imagesc(T,F,abs(S)); axis xy;

The spectrogram plot looks very blurry. What is the most likely cause?

medium

A. Sampling frequency is too low

B. Overlap is too small, causing gaps in data

C. nfft is smaller than window size, causing error

D. Window size is too large, causing poor time resolution

Solution

1. Step 1: Analyze window size effect on resolution

   A large window size (256) smooths over time, reducing time resolution and causing blur.

2. Step 2: Check other parameters

   Overlap is 128 (50%), which is typical and not causing gaps.
   nfft (512) is larger than window (256), which is valid.
   Sampling frequency (1000) is standard.

3. Final Answer:

   Window size is too large, causing poor time resolution -> Option D

4. Quick Check:

   Large window = poor time resolution [OK]

Hint: Large window = better frequency, worse time resolution [OK]

Common Mistakes:

• Confusing overlap with window size effect
• Assuming nfft smaller than window causes blur
• Blaming sampling frequency for blur

5. You want to analyze a signal with rapidly changing frequencies using MATLAB's spectrogram. Which combination of parameters will best capture quick changes without losing frequency detail?

hard

A. Small window size, large overlap, moderate nfft

B. Large window size, large overlap, small nfft

C. Large window size, small overlap, large nfft

D. Small window size, small overlap, large nfft

Solution

1. Step 1: Understand trade-offs in spectrogram parameters

   Small window size improves time resolution to capture rapid changes.
   Large overlap ensures smooth transitions between windows.
   Moderate nfft balances frequency resolution without excessive computation.

2. Step 2: Evaluate options

   Small window size, large overlap, moderate nfft matches these criteria.
   Small window size, small overlap, large nfft has small overlap, causing gaps.
   Options B and C use large windows, reducing time resolution.

3. Final Answer:

   Small window size, large overlap, moderate nfft -> Option A

4. Quick Check:

   Quick changes need small window + large overlap [OK]

Hint: Small window + large overlap = best for fast changes [OK]

Common Mistakes:

• Using large window for fast changes
• Ignoring overlap size
• Choosing too small nfft losing frequency detail