Pole-zero analysis for stability in Signal Processing - Time & Space Complexity

Time Complexity: Pole-zero analysis for stability

O(n)

Understanding Time Complexity

We want to understand how the time to analyze poles and zeros grows as the signal system size increases.

How does the work needed change when we have more poles and zeros to check?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Given poles and zeros as lists
poles = [...]  # list of complex numbers
zeros = [...]  # list of complex numbers

# Check stability by verifying all poles inside unit circle
stable = True
for pole in poles:
    if abs(pole) >= 1:
        stable = False
        break

# Output stability result
print('Stable' if stable else 'Unstable')
    

This code checks if all poles lie inside the unit circle to decide system stability.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each pole to check its magnitude.
• How many times: Once for each pole in the list.

How Execution Grows With Input

As the number of poles increases, the time to check stability grows directly with that number.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The number of operations grows in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to check stability grows directly with the number of poles.

Common Mistake

[X] Wrong: "Checking zeros also adds the same time cost as poles for stability."

[OK] Correct: Stability depends only on poles, so zeros do not affect the time to decide stability.

Interview Connect

Understanding how time grows with system size helps you explain your approach clearly and shows you know what matters most in signal analysis.

Self-Check

"What if we also checked zeros for some property? How would that change the time complexity?"

Practice

1. What does the location of poles inside the unit circle on a pole-zero plot indicate about a system's stability?

easy

A. The system is stable

B. The system is unstable

C. The system is marginally stable

D. The system has no poles

Solution

1. Step 1: Understand pole location and stability

   Poles inside the unit circle mean the system's response decays over time.

2. Step 2: Relate pole location to system behavior

   Since poles are inside the unit circle, the system output will not grow unbounded.

3. Final Answer:

   The system is stable -> Option A

4. Quick Check:

   Poles inside unit circle = stable system [OK]

Hint: Poles inside unit circle mean stability [OK]

Common Mistakes:

• Confusing poles inside with outside the unit circle
• Thinking zeros affect stability directly
• Ignoring the unit circle boundary

2. Which of the following is the correct Python syntax to plot poles and zeros using matplotlib for a system with poles at [0.5+0.5j, 0.5-0.5j] and zeros at [0.8]?

easy

A. plt.scatter([0.5, 0.5], [0.5, -0.5], marker='x', color='r'); plt.scatter([0.8], [0], marker='o', color='b')

B. plt.plot([0.5, 0.5], [0.5, -0.5], 'ro'); plt.plot([0.8], [0], 'bo')

C. plt.scatter([0.5, 0.5], [0.5, -0.5], marker='o', color='b'); plt.scatter([0.8], [0], marker='x', color='r')

D. plt.plot([0.5, 0.5], [0.5, -0.5], 'bx'); plt.plot([0.8], [0], 'ro')

Solution

1. Step 1: Identify correct markers for poles and zeros

   Poles are usually marked with 'x' in red, zeros with 'o' in blue.

2. Step 2: Match syntax with matplotlib scatter function

   plt.scatter([0.5, 0.5], [0.5, -0.5], marker='x', color='r'); plt.scatter([0.8], [0], marker='o', color='b') uses plt.scatter with correct markers and colors for poles and zeros.

3. Final Answer:

   plt.scatter([0.5, 0.5], [0.5, -0.5], marker='x', color='r'); plt.scatter([0.8], [0], marker='o', color='b') -> Option A

4. Quick Check:

   Correct markers and colors for poles and zeros [OK]

Hint: Poles = red 'x', zeros = blue 'o' in plots [OK]

Common Mistakes:

• Swapping markers for poles and zeros
• Using plt.plot with wrong format strings
• Plotting zeros at wrong coordinates

3. Given the poles at [0.9, 1.1] and zeros at [0.5], what will be the stability status of the system?

medium

A. Stable because one pole is inside the unit circle

B. Stable because zeros are inside the unit circle

C. Marginally stable because poles are on the unit circle

D. Unstable because one pole is outside the unit circle

Solution

1. Step 1: Check each pole's location relative to the unit circle

   One pole is at 0.9 (inside), the other at 1.1 (outside) the unit circle.

2. Step 2: Determine stability from pole locations

   Since a pole lies outside the unit circle, the system is unstable regardless of zeros.

3. Final Answer:

   Unstable because one pole is outside the unit circle -> Option D

4. Quick Check:

   Any pole outside unit circle = unstable [OK]

Hint: Any pole outside unit circle means unstable system [OK]

Common Mistakes:

• Ignoring poles outside the unit circle
• Confusing zeros with poles for stability
• Assuming zeros affect stability directly

4. The following Python code attempts to plot poles and zeros but produces an error. What is the error and how to fix it?

import matplotlib.pyplot as plt
poles = [0.7+0.7j, 0.7-0.7j]
zeros = [0.9]
plt.scatter(poles.real, poles.imag, marker='x', color='r')
plt.scatter(zeros.real, zeros.imag, marker='o', color='b')
plt.show()

medium

A. Error because marker symbols are incorrect

B. Error because poles and zeros are lists, need numpy arrays for .real and .imag

C. Error because plt.show() is missing

D. No error, code runs fine

Solution

1. Step 1: Identify data types of poles and zeros

   Poles and zeros are Python lists of complex numbers, which do not support .real or .imag attributes directly.

2. Step 2: Fix by converting lists to numpy arrays

   Convert poles and zeros to numpy arrays to access .real and .imag properties without error.

3. Final Answer:

   Error because poles and zeros are lists, need numpy arrays for .real and .imag -> Option B

4. Quick Check:

   Lists lack .real/.imag; use numpy arrays [OK]

Hint: Use numpy arrays for complex .real and .imag access [OK]

Common Mistakes:

• Trying to access .real on Python lists
• Ignoring missing plt.show()
• Using wrong marker symbols

5. You have a discrete-time system with poles at [0.6, 0.8*1j, -0.8*1j] and zeros at [0.9]. You want to improve stability by moving poles closer to the origin without changing zeros. Which pole movement will make the system more stable?

hard

A. Move poles to [0.6, 0.8j, -0.8j] (no change)

B. Move poles to [1.1, 0.9j, -0.9j]

C. Move poles to [0.4, 0.5j, -0.5j]

D. Move poles to [0.7, 0.85j, -0.85j]

Solution

1. Step 1: Understand stability and pole radius

   Poles closer to origin (smaller magnitude) mean faster decay and better stability.

2. Step 2: Compare given pole movements

   Move poles to [0.4, 0.5j, -0.5j] moves poles closer to origin (0.4 and 0.5j), reducing magnitude from original values.

3. Step 3: Confirm other options increase or keep magnitude same

   Options B and C move poles farther or slightly farther from origin, reducing stability; A is no change.

4. Final Answer:

   Move poles to [0.4, 0.5j, -0.5j] -> Option C

5. Quick Check:

   Smaller pole radius = better stability [OK]

Hint: Move poles closer to origin to improve stability [OK]

Common Mistakes:

• Moving poles outside unit circle
• Changing zeros instead of poles
• Not reducing pole magnitude