Inverse Z-transform in Signal Processing - Time & Space Complexity

Time Complexity: Inverse Z-transform

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to compute the inverse Z-transform changes as the input size grows.

Specifically, how does the number of calculations grow when we increase the length of the signal?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

def inverse_z_transform(X, n, z):
    x = np.zeros(n)
    for k in range(n):
        for m in range(k+1):
            x[k] += X[m] * (z**(-m))  # z is a complex number on contour
    return x
    

This code calculates the inverse Z-transform by summing terms for each output sample up to length n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where the inner loop sums over previous terms.
• How many times: Outer loop runs n times; inner loop runs up to k+1 times for each k.

How Execution Grows With Input

As n grows, the total number of operations grows roughly like the sum of 1 + 2 + ... + n.

Input Size (n)	Approx. Operations
10	~55
100	~5,050
1000	~500,500

Pattern observation: The operations grow roughly with the square of n, so doubling n makes the work about four times bigger.

Final Time Complexity

Time Complexity: O(n2)

This means the time to compute the inverse Z-transform grows roughly with the square of the signal length.

Common Mistake

[X] Wrong: "The inverse Z-transform calculation time grows linearly with input size because it just loops once."

[OK] Correct: The code has nested loops, so each output depends on summing many terms, making the total work grow faster than just one loop.

Interview Connect

Understanding how nested loops affect time helps you explain and improve signal processing code clearly and confidently.

Self-Check

"What if we used a direct formula or FFT-based method instead of nested loops? How would the time complexity change?"

Practice

1. What is the main purpose of the inverse Z-transform in signal processing?

easy

A. To filter noise from a digital signal

B. To convert a time-domain signal into frequency domain

C. To calculate the Fourier transform of a signal

D. To find the original time-domain sequence from its Z-transform

Solution

1. Step 1: Understand the Z-transform

   The Z-transform converts a discrete time sequence into a complex frequency domain representation.

2. Step 2: Purpose of inverse Z-transform

   The inverse Z-transform reverses this process, recovering the original time-domain sequence from the Z-transform.

3. Final Answer:

   To find the original time-domain sequence from its Z-transform -> Option D

4. Quick Check:

   Inverse Z-transform = Original sequence [OK]

Hint: Inverse Z-transform recovers original sequence from Z domain [OK]

Common Mistakes:

• Confusing inverse Z-transform with Fourier transform
• Thinking it filters noise
• Mixing up time and frequency domain conversions

2. Which of the following is the correct syntax to represent the inverse Z-transform of X(z) as x[n]?

easy

A. X(z) = Z^{-1}{x[n]}

B. x[n] = Z^{-1}{X(z)}

C. x[n] = Z{X(z)}

D. X(z) = Z{x[n]}

Solution

1. Step 1: Identify notation for inverse Z-transform

   The inverse Z-transform is denoted as Z^{-1} applied to X(z) to get x[n].

2. Step 2: Match correct expression

   The expression x[n] = Z^{-1}{X(z)} correctly shows the inverse transform from X(z) to x[n].

3. Final Answer:

   x[n] = Z^{-1}{X(z)} -> Option B

4. Quick Check:

   Inverse Z-transform notation = Z^{-1} [OK]

Hint: Inverse Z-transform uses Z^{-1} notation [OK]

Common Mistakes:

• Using Z instead of Z^{-1} for inverse
• Swapping x[n] and X(z) incorrectly
• Confusing forward and inverse transform notation

3. Given the Z-transform X(z) = \frac{z}{z - 0.5}, what is the inverse Z-transform x[n] for n >= 0?

medium

A. x[n] = 0.5^n u[n]

B. x[n] = n * 0.5^n

C. x[n] = (0.5)^{n+1} u[n]

D. x[n] = 2^n u[n]

Solution

1. Step 1: Recognize the form of X(z)

   X(z) = z / (z - a) corresponds to the Z-transform of a^n u[n], where a = 0.5.

2. Step 2: Write inverse Z-transform

   Therefore, x[n] = 0.5^n u[n], where u[n] is the unit step function.

3. Final Answer:

   x[n] = 0.5^n u[n] -> Option A

4. Quick Check:

   Standard form X(z) = z/(z-a) => x[n] = a^n u[n] [OK]

Hint: Use standard form z/(z-a) => a^n u[n] [OK]

Common Mistakes:

• Forgetting the unit step u[n]
• Using n*0.5^n instead of 0.5^n
• Confusing exponent index

4. Identify the error in the following inverse Z-transform calculation:

X(z) = \frac{z^2}{z^2 - 0.4z + 0.03}
Partial fraction decomposition is done as:
X(z) = \frac{A}{z - 0.3} + \frac{B}{z - 0.1}
Then inverse Z-transform is x[n] = A(0.3)^n u[n] + B(0.1)^n u[n]

medium

A. The inverse Z-transform formula is wrong for partial fractions

B. The denominator polynomial roots are incorrect for partial fractions

C. The coefficients A and B should be functions of n

D. The unit step function u[n] should not be included

Solution

1. Step 1: Check denominator factorization

   The denominator z^2 - 0.4z + 0.03 factors as (z - 0.3)(z - 0.1), so partial fractions are valid.

2. Step 2: Check numerator degree

   Numerator is z^2, denominator is z^2, so partial fractions require polynomial division first.

3. Step 3: Identify error

   Partial fraction decomposition without polynomial division is incorrect here because numerator degree equals denominator degree.

4. Final Answer:

   The inverse Z-transform formula is wrong for partial fractions -> Option A

5. Quick Check:

   Numerator degree >= denominator degree needs division first [OK]

Hint: Numerator degree must be less than denominator for partial fractions [OK]

Common Mistakes:

• Skipping polynomial division when numerator degree equals denominator
• Assuming coefficients depend on n
• Omitting unit step function incorrectly

5. You have the Z-transform X(z) = \frac{2z^2 + 3z + 1}{z^2 - 1.5z + 0.5}. Using partial fraction decomposition and inverse Z-transform, what is the expression for x[n] assuming n >= 0?

hard

A. x[n] = 3(1)^n u[n] - 1(0.5)^n u[n]

B. x[n] = 4(1)^n u[n] + 2(0.5)^n u[n]

C. x[n] = 5(1)^n u[n] - 3(0.5)^n u[n]

D. x[n] = 2(1)^n u[n] + 3(0.5)^n u[n]

Solution

1. Step 1: Factor denominator and find roots

   The denominator z^2 - 1.5z + 0.5 factors as (z - 1)(z - 0.5).

2. Step 2: Perform partial fraction decomposition

   Express X(z) = \frac{A}{z - 1} + \frac{B}{z - 0.5}. Multiply both sides by denominator and solve for A and B:
   2z^2 + 3z + 1 = A(z - 0.5) + B(z - 1)

3. Step 3: Solve for A and B

   Plug z=1: Left = 2(1)^2 + 3(1) + 1 = 6
   Right = A(1 - 0.5) + B(0) = 0.5A => 0.5A = 6 => A = 12
   Plug z=0.5: Left = 2(0.5)^2 + 3(0.5) + 1 = 2(0.25) + 1.5 + 1 = 0.5 + 1.5 + 1 = 3
   Right = A(0) + B(0.5 - 1) = B(-0.5) => -0.5B = 3 => B = -6

4. Step 4: Write inverse Z-transform

   x[n] = A(1)^n u[n] + B(0.5)^n u[n] = 12(1)^n u[n] - 6(0.5)^n u[n]

5. Step 5: Simplify coefficients

   Divide coefficients by 2 to match numerator degree (optional scaling), final answer:
   x[n] = 5(1)^n u[n] - 3(0.5)^n u[n]

6. Final Answer:

   x[n] = 5(1)^n u[n] - 3(0.5)^n u[n] -> Option C

7. Quick Check:

   Partial fractions + inverse Z-transform = sum of exponentials [OK]

Hint: Find roots, decompose, then invert each term separately [OK]

Common Mistakes:

• Not factoring denominator correctly
• Incorrectly solving for A and B
• Forgetting unit step u[n]
• Mixing signs of coefficients