Magnitude and phase spectrum in Signal Processing - Time & Space Complexity

Time Complexity: Magnitude and phase spectrum

O(n log n)

Understanding Time Complexity

When we compute the magnitude and phase spectrum of a signal, we want to know how the time to do this grows as the signal gets longer.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

def magnitude_phase_spectrum(signal):
    fft_result = np.fft.fft(signal)
    magnitude = np.abs(fft_result)
    phase = np.angle(fft_result)
    return magnitude, phase

This code computes the FFT of a signal, then finds the magnitude and phase for each frequency component.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The FFT algorithm processes the entire input signal.
• How many times: The FFT uses a divide-and-conquer approach, working on smaller parts repeatedly until done.
• Additional operations: Calculating magnitude and phase loops through all FFT results once each.

How Execution Grows With Input

As the signal length grows, the FFT work grows a bit faster than the signal size but much slower than doing all pairs.

Input Size (n)	Approx. Operations
10	About 30 operations
100	About 700 operations
1000	About 10,000 operations

Pattern observation: The operations grow a little more than linearly, roughly n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means if the signal doubles in length, the work grows a bit more than double, but not as much as if we did every pair.

Common Mistake

[X] Wrong: "Calculating magnitude and phase takes as much time as the FFT itself."

[OK] Correct: Magnitude and phase calculations just loop once through the FFT output, which is much faster than the FFT process.

Interview Connect

Understanding how FFT scales helps you explain efficient signal processing in real projects, showing you know how to handle large data smoothly.

Self-Check

"What if we used a slower DFT algorithm instead of FFT? How would the time complexity change?"

Practice

1. What does the magnitude spectrum represent in signal processing?

easy

A. The strength or amplitude of different frequency components

B. The timing or phase shift of frequency components

C. The original time-domain signal values

D. The noise level in the signal

Solution

1. Step 1: Understand magnitude spectrum meaning

   The magnitude spectrum shows how strong or intense each frequency is in a signal.

2. Step 2: Differentiate from phase spectrum

   The phase spectrum shows timing, not strength, so it is not the magnitude.

3. Final Answer:

   The strength or amplitude of different frequency components -> Option A

4. Quick Check:

   Magnitude spectrum = strength [OK]

Hint: Magnitude = strength of frequencies, phase = timing [OK]

Common Mistakes:

• Confusing magnitude with phase
• Thinking magnitude shows time values
• Mixing magnitude with noise level

2. Which Python function is used to get the phase spectrum from a Fourier Transform result stored in variable F?

easy

A. np.abs(F)

B. np.angle(F)

C. np.fft(F)

D. np.real(F)

Solution

1. Step 1: Recall phase extraction function

   In Python's NumPy, np.angle() returns the phase angles of complex numbers.

2. Step 2: Differentiate from magnitude and other functions

   np.abs() returns magnitude, np.fft() is not a valid function, and np.real() returns real parts only.

3. Final Answer:

   np.angle(F) -> Option B

4. Quick Check:

   Phase spectrum = np.angle() [OK]

Hint: Use np.angle() for phase, np.abs() for magnitude [OK]

Common Mistakes:

• Using np.abs() instead of np.angle() for phase
• Trying to use np.fft() which is invalid
• Confusing real part with phase

3. Given the code:

import numpy as np
x = np.array([1, 0, -1, 0])
F = np.fft.fft(x)
magnitude = np.abs(F)
phase = np.angle(F)
print(np.round(magnitude, 2))
print(np.round(phase, 2))

What is the printed magnitude and phase arrays?

medium

A. [4.00 0.00 0.00 0.00]
[0.00 0.00 0.00 0.00]

B. [0.00 2.00 0.00 2.00]
[0.00 0.00 0.00 0.00]

C. [2.00 2.00 2.00 2.00]
[ 0.00 -1.57 3.14 1.57]

D. [2.00 0.00 2.00 0.00]
[0.00 1.57 3.14 -1.57]

Solution

1. Step 1: Compute FFT of x

   The FFT of [1, 0, -1, 0] is [0+0j, 2+0j, 0+0j, 2+0j].

2. Step 2: Calculate magnitude and phase arrays

   Magnitude is [2.00 2.00 2.00 2.00]. Phase angles are [0.00 -1.57 3.14 1.57].

3. Final Answer:

   [2.00 2.00 2.00 2.00] [ 0.00 -1.57 3.14 1.57] -> Option C

4. Quick Check:

   Magnitude = [2 2 2 2], Phase = approx [-pi/2, pi, pi/2] [OK]

Hint: FFT magnitude is abs(), phase is angle() in radians [OK]

Common Mistakes:

• Confusing magnitude with real part
• Not rounding phase correctly
• Mixing up signs of phase angles

4. The following code attempts to compute magnitude and phase but has an error:

import numpy as np
x = np.array([1, 2, 3, 4])
F = np.fft.fft(x)
magnitude = np.angle(F)
phase = np.abs(F)
print(magnitude)
print(phase)

What is the error?

medium

A. No error; code runs correctly

B. np.fft.fft() is used incorrectly; should be np.fft.ifft()

C. The input array x must be complex numbers

D. Magnitude and phase are swapped; np.angle() should be for phase, np.abs() for magnitude

Solution

1. Step 1: Check function usage for magnitude and phase

   Magnitude is the absolute value, so np.abs() should be used for magnitude, not np.angle(). Phase is angle, so np.angle() is for phase.

2. Step 2: Identify swapped assignments

   The code assigns magnitude = np.angle(F) and phase = np.abs(F), which is reversed.

3. Final Answer:

   Magnitude and phase are swapped; np.angle() should be for phase, np.abs() for magnitude -> Option D

4. Quick Check:

   Magnitude = abs(), Phase = angle() [OK]

Hint: Remember: abs() for magnitude, angle() for phase [OK]

Common Mistakes:

• Swapping magnitude and phase functions
• Thinking FFT input must be complex
• Confusing FFT and IFFT usage

5. You have a noisy signal and want to keep only frequencies with magnitude above 5. Which steps correctly apply this filter using FFT results stored in F?

hard

A. Calculate magnitude = np.abs(F), create mask = magnitude > 5, then set F_filtered = F * mask

B. Calculate phase = np.angle(F), create mask = phase > 5, then set F_filtered = F * mask

C. Calculate magnitude = np.abs(F), create mask = magnitude < 5, then set F_filtered = F * mask

D. Calculate magnitude = np.abs(F), create mask = magnitude > 5, then set F_filtered = np.abs(F) * mask

Solution

1. Step 1: Compute magnitude and create mask

   Calculate magnitude with np.abs(F). Create a boolean mask where magnitude > 5 to keep strong frequencies.

2. Step 2: Apply mask to original FFT data

   Multiply the complex FFT array F by the mask to zero out weak frequencies, preserving phase and magnitude of strong ones.

3. Final Answer:

   Calculate magnitude = np.abs(F), create mask = magnitude > 5, then set F_filtered = F * mask -> Option A

4. Quick Check:

   Filter by magnitude > 5, multiply mask with F [OK]

Hint: Filter frequencies by magnitude mask, multiply mask with FFT [OK]

Common Mistakes:

• Filtering by phase instead of magnitude
• Using magnitude < 5 to keep frequencies
• Multiplying mask with magnitude only, losing phase info