IIR filter design (butter, cheby1) in SciPy - Time & Space Complexity

Time Complexity: IIR filter design (butter, cheby1)

O(n^3)

Understanding Time Complexity

When designing IIR filters using scipy, it is important to understand how the time to compute the filter coefficients grows as the filter order increases.

We want to know how the computation time changes when we ask for more precise or complex filters.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.signal import butter, cheby1

# Design a Butterworth filter
b, a = butter(N=order, Wn=0.3, btype='low')

# Design a Chebyshev Type I filter
b_c, a_c = cheby1(N=order, rp=1, Wn=0.3, btype='low')

This code designs low-pass IIR filters of a given order using two common methods.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Computing polynomial coefficients involves matrix operations and recursive calculations related to filter order.
• How many times: The main calculations repeat roughly proportional to the filter order order, as each order adds complexity to the polynomial computations.

How Execution Grows With Input

As the filter order increases, the number of calculations grows roughly in proportion to the cube of the order.

Input Size (order)	Approx. Operations
10	~1,000
100	~1,000,000
1000	~1,000,000,000

Pattern observation: Doubling the filter order roughly multiplies the number of operations by eight.

Final Time Complexity

Time Complexity: O(n^3)

This means that if you double the filter order, the time to compute the filter coefficients will increase about eight times.

Common Mistake

[X] Wrong: "The filter design time grows linearly with filter order because it just calculates coefficients once."

[OK] Correct: The calculations involve polynomial operations that combine terms repeatedly, causing the time to grow faster than just linearly.

Interview Connect

Understanding how algorithm time grows with input size helps you explain and reason about performance in real data science tasks, like signal processing.

Self-Check

"What if we used a different filter design method that uses iterative optimization instead of polynomial calculations? How would the time complexity change?"

Practice

1. What is the main difference between a Butterworth and a Chebyshev IIR filter in scipy.signal?

easy

A. Butterworth filters are FIR, Chebyshev filters are IIR.

B. Butterworth filters have ripples, Chebyshev filters have a smooth response.

C. Butterworth filters are only for high-pass, Chebyshev only for low-pass.

D. Butterworth filters have a smooth frequency response, Chebyshev filters have ripples in the passband.

Solution

1. Step 1: Understand Butterworth filter characteristics

   Butterworth filters are designed to have a maximally flat frequency response in the passband, meaning no ripples.

2. Step 2: Understand Chebyshev filter characteristics

   Chebyshev filters allow ripples in the passband to achieve a sharper cutoff compared to Butterworth filters.

3. Final Answer:

   Butterworth filters have a smooth frequency response, Chebyshev filters have ripples in the passband. -> Option D

4. Quick Check:

   Butterworth smooth, Chebyshev ripples = D [OK]

Hint: Butterworth = smooth, Chebyshev = ripples [OK]

Common Mistakes:

• Confusing which filter has ripples
• Thinking Butterworth is FIR
• Assuming filter types are limited to passband types

2. Which of the following is the correct way to design a 4th order Butterworth lowpass filter with cutoff frequency 0.3 (normalized) using scipy.signal.butter?

easy

A. b, a = butter(0.3, 4, btype='low')

B. b, a = butter(4, 0.3, btype='low')

C. b, a = butter(4, 0.3, type='lowpass')

D. b, a = butter(order=4, cutoff=0.3, kind='low')

Solution

1. Step 1: Recall butter function signature

   The function signature is butter(N, Wn, btype='low', analog=False, output='ba'), where N is order and Wn is cutoff frequency.

2. Step 2: Check correct parameter usage

   b, a = butter(4, 0.3, btype='low') uses butter(4, 0.3, btype='low'), which matches the signature correctly.

3. Final Answer:

   b, a = butter(4, 0.3, btype='low') -> Option B

4. Quick Check:

   Order first, cutoff second, btype='low' = A [OK]

Hint: Order first, cutoff second, btype='low' in butter() [OK]

Common Mistakes:

• Swapping order and cutoff parameters
• Using wrong keyword names like 'type' or 'kind'
• Passing cutoff frequency as first argument

3. What will be the output shape of the coefficients when running this code?

from scipy.signal import cheby1
b, a = cheby1(3, 1, 0.4, btype='high')

medium

A. (3,), (3,)

B. (3, 3), (3, 3)

C. (4,), (4,)

D. (2,), (2,)

Solution

1. Step 1: Understand cheby1 output

   The function returns numerator (b) and denominator (a) coefficients arrays each of length N+1, where N is filter order.

2. Step 2: Calculate length for order 3

   For order 3, length is 3+1 = 4, so both b and a have shape (4,).

3. Final Answer:

   (4,), (4,) -> Option C

4. Quick Check:

   Length = order + 1 = 4 [OK]

Hint: Coefficients length = order + 1 [OK]

Common Mistakes:

• Assuming length equals order
• Expecting 2D arrays instead of 1D
• Confusing numerator and denominator shapes

4. Identify the error in this code snippet for designing a Chebyshev type I filter:

from scipy.signal import cheby1
b, a = cheby1(5, 0.5, 0.2, btype='bandpass')

medium

A. The cutoff frequency should be a list or tuple for bandpass, not a single float.

B. The ripple parameter is missing and required.

C. The order parameter should be a float, not integer.

D. The btype 'bandpass' is not supported by cheby1.

Solution

1. Step 1: Check bandpass cutoff frequency format

   For bandpass filters, cutoff frequency must be a sequence (list or tuple) of two frequencies, not a single float.

2. Step 2: Verify other parameters

   Order as integer and ripple (second parameter) are correctly provided; btype 'bandpass' is valid.

3. Final Answer:

   The cutoff frequency should be a list or tuple for bandpass, not a single float. -> Option A

4. Quick Check:

   Bandpass cutoff needs two frequencies = C [OK]

Hint: Bandpass cutoff must be two frequencies in a list/tuple [OK]

Common Mistakes:

• Passing single float for bandpass cutoff
• Confusing ripple parameter position
• Using unsupported btype values

5. You want to design a Chebyshev type I lowpass filter with order 6, 0.5 dB ripple, and cutoff frequency 0.25. Which code snippet correctly creates the filter and applies it to a signal x using scipy.signal.lfilter?

hard

A. from scipy.signal import cheby1, lfilter
b, a = cheby1(6, 0.5, 0.25, btype='low')
y = lfilter(b, a, x)

B. from scipy.signal import cheby1, lfilter
b, a = cheby1(6, 0.5, 0.25, btype='high')
y = lfilter(a, b, x)

C. from scipy.signal import butter, lfilter
b, a = butter(6, 0.25, btype='low')
y = lfilter(b, a, x)

D. from scipy.signal import cheby1, lfilter
b, a = cheby1(0.5, 6, 0.25, btype='low')
y = lfilter(b, a, x)

Solution

1. Step 1: Verify cheby1 parameters order

   Order is first parameter (6), ripple second (0.5), cutoff third (0.25), and btype='low' for lowpass.

2. Step 2: Check lfilter usage

   lfilter takes numerator coefficients (b), denominator coefficients (a), and signal (x) in that order.

3. Final Answer:

   from scipy.signal import cheby1, lfilter b, a = cheby1(6, 0.5, 0.25, btype='low') y = lfilter(b, a, x) -> Option A

4. Quick Check:

   Correct order and lfilter usage = A [OK]

Hint: Order, ripple, cutoff in cheby1; lfilter(b, a, x) [OK]

Common Mistakes:

• Swapping order and ripple parameters
• Using butter instead of cheby1
• Swapping b and a in lfilter