Stability analysis (pole-zero plot) in Signal Processing - Time & Space Complexity

Time Complexity: Stability analysis (pole-zero plot)

O(n^3)

Understanding Time Complexity

We want to understand how the time to analyze system stability grows as the system size increases.

Specifically, we ask: How does checking poles and zeros scale with input size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.signal import tf2zpk

# Given numerator and denominator coefficients
num = np.array([1, -0.5, 0.25])
den = np.array([1, -1.2, 0.36])

# Compute zeros, poles, and gain
zeros, poles, gain = tf2zpk(num, den)

# Check stability by examining poles
stable = np.all(np.abs(poles) < 1)
    

This code finds poles and zeros of a system and checks if all poles lie inside the unit circle to decide stability.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Finding roots of the denominator polynomial (poles).
• How many times: The root-finding algorithm processes all coefficients once, internally using iterative methods.

How Execution Grows With Input

As the polynomial degree (input size) grows, root-finding takes more time because it must handle more coefficients.

Input Size (degree n)	Approx. Operations
10	About 1,000 operations
100	About 1,000,000 operations
1000	About 1,000,000,000 operations

Pattern observation: Operations grow roughly with the cube of the polynomial degree.

Final Time Complexity

Time Complexity: O(n^3)

This means the time to find poles grows roughly with the cube of the number of coefficients.

Common Mistake

[X] Wrong: "Finding poles is a simple linear scan and takes O(n) time."

[OK] Correct: Root-finding involves complex iterative calculations that grow faster than linearly with polynomial degree.

Interview Connect

Understanding how stability checks scale helps you explain system analysis efficiency clearly and confidently.

Self-Check

"What if we used a simpler method that only approximates poles? How would the time complexity change?"

Practice

1. What does it mean for a system to be stable in terms of its poles on the pole-zero plot?

easy

A. All poles must lie in the left half of the complex plane (negative real parts).

B. All poles must lie on the imaginary axis.

C. All zeros must lie in the right half of the complex plane.

D. Poles and zeros must be equal in number.

Solution

1. Step 1: Understand pole location and stability

   Stability depends on poles, not zeros. Poles with negative real parts mean the system's response decays over time.

2. Step 2: Identify correct pole location for stability

   Poles in the left half-plane (negative real parts) ensure the system is stable.

3. Final Answer:

   All poles must lie in the left half of the complex plane (negative real parts). -> Option A

4. Quick Check:

   Stable system = poles with negative real parts [OK]

Hint: Stable system means poles left of imaginary axis [OK]

Common Mistakes:

• Confusing zeros with poles for stability
• Thinking poles on imaginary axis are stable
• Assuming zeros affect stability directly

2. Which of the following is the correct Python syntax to plot poles and zeros using the scipy.signal library?

easy

A. signal.pzmap(system, plot=True)

B. signal.pzplot(system)

C. signal.pzplot(system, plot=True)

D. signal.pzmap(system, plot=False)

Solution

1. Step 1: Recall scipy.signal function for pole-zero plot

   The function to plot poles and zeros is pzmap, not pzplot.

2. Step 2: Check correct usage with plotting enabled

   Using pzmap with plot=True plots the pole-zero map correctly.

3. Final Answer:

   signal.pzmap(system, plot=True) -> Option A

4. Quick Check:

   Use pzmap with plot=True for pole-zero plot [OK]

Hint: Use pzmap with plot=True to plot poles and zeros [OK]

Common Mistakes:

• Using non-existent function pzplot
• Forgetting plot=True argument
• Confusing function names

3. Given the poles of a system as poles = [-1+2j, -1-2j, 0.5], what can you say about the system's stability?

medium

A. The system is stable because poles are complex conjugates.

B. The system is stable because all poles have negative real parts.

C. The system is marginally stable because poles are on the imaginary axis.

D. The system is unstable because one pole has a positive real part.

Solution

1. Step 1: Analyze the real parts of each pole

   Poles are -1+2j (real part -1), -1-2j (real part -1), and 0.5 (real part 0.5).

2. Step 2: Determine stability from pole real parts

   Since one pole has positive real part (0.5), the system is unstable.

3. Final Answer:

   The system is unstable because one pole has a positive real part. -> Option D

4. Quick Check:

   Positive real pole means unstable system [OK]

Hint: Check if any pole has positive real part for instability [OK]

Common Mistakes:

• Ignoring positive real part pole
• Assuming complex conjugates guarantee stability
• Confusing marginal stability with instability

4. The following Python code attempts to plot poles and zeros but gives an error:

from scipy import signal
system = signal.TransferFunction([1, 3], [1, 2, 1])
signal.pzplot(system)

What is the error and how to fix it?

medium

A. TransferFunction requires discrete=True for pzplot to work.

B. TransferFunction arguments are reversed; swap numerator and denominator.

C. Function pzplot does not exist; use pzmap(system, plot=True) instead.

D. Import statement is wrong; use import scipy.signal as signal.

Solution

1. Step 1: Identify the function causing error

   The function pzplot does not exist in scipy.signal, causing the error.

2. Step 2: Use correct function to plot poles and zeros

   Use pzmap(system, plot=True) to plot poles and zeros correctly.

3. Final Answer:

   Function pzplot does not exist; use pzmap(system, plot=True) instead. -> Option C

4. Quick Check:

   Use pzmap, not pzplot, for pole-zero plots [OK]

Hint: Use pzmap with plot=True, not pzplot [OK]

Common Mistakes:

• Using non-existent pzplot function
• Swapping numerator and denominator unnecessarily
• Wrong import statement causing confusion

5. You have a system with poles at -0.5, -1+1j, -1-1j and zeros at 0, -2. Which statement best describes the system's stability and response?

hard

A. The system is marginally stable because of zeros at zero.

B. The system is stable with oscillatory decay due to complex poles.

C. The system is unstable because zeros are on the right half-plane.

D. The system is unstable due to poles with positive real parts.

Solution

1. Step 1: Check pole locations for stability

   All poles have negative real parts (-0.5, -1), so system is stable.

2. Step 2: Analyze pole types for response behavior

   Complex conjugate poles (-1±1j) cause oscillations that decay over time.

3. Step 3: Consider zeros' effect on stability

   Zeros do not affect stability directly; zeros at 0 and -2 are not in right half-plane.

4. Final Answer:

   The system is stable with oscillatory decay due to complex poles. -> Option B

5. Quick Check:

   Negative real poles + complex = stable oscillatory decay [OK]

Hint: Stable if poles negative; complex poles cause oscillations [OK]

Common Mistakes:

• Confusing zeros with poles for stability
• Thinking zeros at zero cause instability
• Ignoring oscillatory nature of complex poles