Transfer function H(z) in Signal Processing - Time & Space Complexity

Time Complexity: Transfer function H(z)

O(n * m)

Understanding Time Complexity

We want to understand how the time to compute the transfer function H(z) changes as the input size grows.

How does the number of calculations grow when we increase the length of the input signal or filter coefficients?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Compute output y[n] using transfer function H(z)
for n in range(len(x)):
    y[n] = 0
    for k in range(len(h)):
        if n - k >= 0:
            y[n] += h[k] * x[n - k]

This code calculates the output signal y by applying the filter coefficients h to the input signal x using convolution.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops performing multiplications and additions for convolution.
• How many times: Outer loop runs for each input sample (n times), inner loop runs for each filter coefficient (m times).

How Execution Grows With Input

As the input size or filter length grows, the total operations increase by multiplying these sizes.

Input Size (n)	Filter Length (m)	Approx. Operations
10	5	50
100	5	500
1000	5	5000

Pattern observation: Operations grow proportionally to the product of input size and filter length.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to compute grows in direct proportion to both the input length and the filter size.

Common Mistake

[X] Wrong: "The time to compute H(z) depends only on the input size n."

[OK] Correct: The filter length m also affects the total work because each input sample is combined with all filter coefficients.

Interview Connect

Understanding how nested loops affect time helps you explain performance in signal processing tasks clearly and confidently.

Self-Check

"What if the filter length m is fixed and very small? How would the time complexity change as input size n grows?"