FFT and frequency analysis in MATLAB - Time & Space Complexity

Time Complexity: FFT and frequency analysis

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to perform FFT changes as the input size grows.

How does the number of steps grow when we analyze more data points?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

N = 1024;
x = rand(1, N);
X = fft(x);
    

This code generates a random signal of length N and computes its FFT to analyze frequency components.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The FFT algorithm repeatedly combines pairs of data points through stages.
• How many times: The process repeats about log₂(N) times, each stage processing all N points.

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 33
100	About 664
1000	About 9966

Pattern observation: The operations grow roughly like n times log n, which is slower than n squared but faster than just n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the input size but much slower than checking every pair of points.

Common Mistake

[X] Wrong: "FFT takes as long as multiplying every pair of points, so it is O(n²)."

[OK] Correct: FFT cleverly reuses calculations in stages, so it avoids doing all pairs and runs much faster.

Interview Connect

Knowing how FFT scales helps you explain efficient signal processing and shows you understand smart algorithms that save time.

Self-Check

"What if we used a simple discrete Fourier transform (DFT) instead of FFT? How would the time complexity change?"

Practice

1. What does the MATLAB function fft() do to a signal?

easy

A. It amplifies the signal amplitude.

B. It converts the signal from time domain to frequency domain.

C. It smooths the signal to remove noise.

D. It shifts the signal in time.

Solution

1. Step 1: Understand the purpose of FFT

   FFT stands for Fast Fourier Transform, which changes a signal from time domain to frequency domain.

2. Step 2: Identify what fft() does in MATLAB

   In MATLAB, fft() computes the discrete Fourier transform, showing frequency components of the signal.

3. Final Answer:

   It converts the signal from time domain to frequency domain. -> Option B

4. Quick Check:

   FFT = frequency transform [OK]

Hint: FFT always changes time signals to frequency signals [OK]

Common Mistakes:

• Thinking FFT smooths or filters signals
• Confusing FFT with time shifting
• Assuming FFT amplifies signal amplitude

2. Which of the following is the correct syntax to compute the FFT of a vector x in MATLAB?

easy

A. Y = fft x;

B. Y = fft[x];

C. Y = fft(x);

D. Y = fft{x};

Solution

1. Step 1: Recall MATLAB function call syntax

   In MATLAB, functions are called with parentheses enclosing arguments, e.g., func(arg).

2. Step 2: Check each option's syntax

   Y = fft(x); uses correct syntax: fft(x). Options A, C, and D use invalid syntax for function calls in MATLAB.

3. Final Answer:

   Y = fft(x); -> Option C

4. Quick Check:

   Function calls use parentheses () [OK]

Hint: Use parentheses () for function calls in MATLAB [OK]

Common Mistakes:

• Using square brackets [] instead of parentheses
• Omitting parentheses around arguments
• Using curly braces {} which are for cell arrays

3. Given the MATLAB code:

x = [1 1 0 0];
Y = fft(x);
absY = abs(Y);
disp(absY);

What is the output displayed?

medium

A. [1 1 1 1]

B. [2 0 2 0]

C. [4 0 0 0]

D. [2 1.4142 0 1.4142]

Solution

1. Step 1: Compute FFT of x = [1 1 0 0]

   The FFT of this sequence results in complex values whose magnitudes are [2, sqrt(2), 0, sqrt(2)] approximately.

2. Step 2: Calculate absolute values

   Taking absolute values gives approximately [2, 1.4142, 0, 1.4142].

3. Final Answer:

   [2 1.4142 0 1.4142] -> Option D

4. Quick Check:

   FFT magnitude matches [2 1.4142 0 1.4142] [OK]

Hint: FFT magnitude shows signal strength at each frequency [OK]

Common Mistakes:

• Confusing FFT output with original signal
• Not taking absolute value before display
• Assuming FFT output is all real numbers

4. Consider this MATLAB code snippet:

Fs = 1000;
t = 0:1/Fs:1-1/Fs;
x = cos(2*pi*50*t) + cos(2*pi*120*t);
Y = fft(x);
P2 = abs(Y/length(x));
P1 = P2(1:length(x)/2+1);
P1(2:end-1) = 2*P1(2:end-1);
plot(P1);

What is the likely error in this code?

medium

A. The frequency axis is missing for the plot, so frequencies are unclear.

B. The length of x is not used correctly in dividing Y.

C. The FFT function is called incorrectly without arguments.

D. The signal x is not defined properly.

Solution

1. Step 1: Analyze the FFT and amplitude spectrum calculation

   The code correctly computes the single-sided amplitude spectrum P1 from Y.

2. Step 2: Check the plot command

   The plot shows amplitude values but does not label or define the frequency axis, making interpretation difficult.

3. Final Answer:

   The frequency axis is missing for the plot, so frequencies are unclear. -> Option A

4. Quick Check:

   Plot frequency axis needed for clarity [OK]

Hint: Always plot frequency axis with amplitude spectrum [OK]

Common Mistakes:

• Forgetting to create frequency vector for x-axis
• Plotting amplitude without frequency labels
• Misusing FFT input or output sizes

5. You have a noisy signal sampled at 1000 Hz stored in vector data. You want to find the dominant frequency component using FFT. Which MATLAB code snippet correctly computes and plots the single-sided amplitude spectrum with frequency axis?

hard

A. L = length(data); Fs = 1000; Y = fft(data); P2 = abs(Y/L); f = Fs*(0:(L/2))/L; P1 = P2(1:L/2+1); P1(2:end-1) = 2*P1(2:end-1); plot(f,P1); xlabel('Frequency (Hz)'); ylabel('Amplitude');

B. Fs = 1000; Y = fft(data); plot(abs(Y)); xlabel('Frequency'); ylabel('Amplitude');

C. L = length(data); Y = fft(data); P1 = abs(Y); plot(P1);

D. Fs = 1000; t = 0:1/Fs:1; Y = fft(data); plot(Y);

Solution

1. Step 1: Understand the steps to compute single-sided amplitude spectrum

   Calculate FFT, normalize by length, create frequency vector, extract half spectrum, double amplitudes except DC and Nyquist.

2. Step 2: Check which option follows these steps correctly

   L = length(data); Fs = 1000; Y = fft(data); P2 = abs(Y/L); f = Fs*(0:(L/2))/L; P1 = P2(1:L/2+1); P1(2:end-1) = 2*P1(2:end-1); plot(f,P1); xlabel('Frequency (Hz)'); ylabel('Amplitude'); correctly computes length, frequency vector, normalizes, adjusts amplitudes, and plots with labels. Others miss frequency axis or normalization.

3. Final Answer:

   Option A code snippet -> Option A

4. Quick Check:

   Proper FFT amplitude spectrum needs frequency axis and normalization [OK]

Hint: Normalize FFT and plot with frequency vector for correct spectrum [OK]

Common Mistakes:

• Not normalizing FFT by signal length
• Plotting full FFT without single-sided spectrum
• Missing frequency axis in plot