Applying filters (lfilter, sosfilt) in SciPy - Time & Space Complexity

Time Complexity: Applying filters (lfilter, sosfilt)

O(n)

Understanding Time Complexity

When we use scipy to apply filters on signals, it is important to know how the time taken grows as the signal gets longer.

We want to understand how the filtering process scales with input size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.signal import lfilter

b = [0.2, 0.2, 0.2, 0.2, 0.2]  # filter coefficients
x = np.random.rand(1000)       # input signal

y = lfilter(b, [1.0], x)       # apply filter
    

This code applies a simple moving average filter to a signal of length 1000.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each output element, multiply and sum filter coefficients with input elements.
• How many times: This happens once for each element in the input signal.

How Execution Grows With Input

As the input signal length grows, the number of operations grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 50 (10 elements x 5 coefficients)
100	About 500 (100 x 5)
1000	About 5000 (1000 x 5)

Pattern observation: Operations increase linearly as input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to filter grows directly with the length of the input signal.

Common Mistake

[X] Wrong: "Filtering takes the same time no matter how long the signal is."

[OK] Correct: The filter must process each input element, so longer signals take more time.

Interview Connect

Understanding how filtering scales helps you explain performance in real signal processing tasks.

Self-Check

"What if we change the filter length to be proportional to the input size? How would the time complexity change?"