Common Z-transform pairs in Signal Processing - Time & Space Complexity

Time Complexity: Common Z-transform pairs

O(n)

Understanding Time Complexity

We want to understand how the time to find Z-transform pairs grows as the input size increases.

How does the number of operations change when we use common Z-transform pairs for longer sequences?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Example: Compute Z-transform of a finite sequence using common pairs
function zTransform(sequence, z) {
  let result = 0;
  for (let n = 0; n < sequence.length; n++) {
    result += sequence[n] * Math.pow(z, -n);
  }
  return result;
}
    

This code calculates the Z-transform by summing terms of the input sequence multiplied by powers of z.

Identify Repeating Operations

• Primary operation: Loop over each element of the input sequence.
• How many times: Once for each element in the sequence (n times).

How Execution Grows With Input

As the sequence length grows, the number of operations grows linearly.

Input Size (n)	Approx. Operations
10	10 additions and multiplications
100	100 additions and multiplications
1000	1000 additions and multiplications

Pattern observation: Doubling the input size roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute the Z-transform grows directly with the length of the input sequence.

Common Mistake

[X] Wrong: "Using common Z-transform pairs makes the computation instant regardless of input size."

[OK] Correct: Even with known pairs, computing the transform for longer sequences still requires processing each element, so time grows with input length.

Interview Connect

Understanding how computation time grows with input size helps you explain your approach clearly and shows you know how to handle larger data efficiently.

Self-Check

"What if we used a recursive formula to compute the Z-transform instead of a loop? How would the time complexity change?"

Practice

1. Which of the following is the Z-transform of the sequence x[n] = a^n u[n], where u[n] is the unit step?

easy

A. X(z) = z / (z - a), |z| < |a|

B. X(z) = 1 / (1 - a z^{-1}), |z| > |a|

C. X(z) = (1 - a z^{-1}) / z, |z| > |a|

D. X(z) = a / (1 - z^{-1}), |z| > 1

Solution

1. Step 1: Recall the definition of the Z-transform for geometric sequences

   The Z-transform of a^n u[n] is a standard pair given by the sum of a geometric series: \( \sum_{n=0}^\infty a^n z^{-n} = \frac{1}{1 - a z^{-1}} \) for \( |z| > |a| \).

2. Step 2: Match the formula with the options

   X(z) = 1 / (1 - a z^{-1}), |z| > |a| matches the formula exactly with the correct region of convergence.

3. Final Answer:

   X(z) = 1 / (1 - a z^{-1}), |z| > |a| -> Option B

4. Quick Check:

   Geometric sequence Z-transform = 1/(1 - a z^{-1}) [OK]

Hint: Geometric sequences transform to 1/(1 - a z^{-1}) [OK]

Common Mistakes:

• Confusing region of convergence
• Mixing numerator and denominator terms
• Using wrong inequality for |z|

2. Which of the following is the correct Z-transform expression for the unit impulse sequence δ[n]?

easy

A. X(z) = z / (z - 1)

B. X(z) = z^{-1}

C. X(z) = 1 / (1 - z^{-1})

D. X(z) = 1

Solution

1. Step 1: Understand the unit impulse sequence

   The unit impulse δ[n] is 1 at n=0 and 0 elsewhere.

2. Step 2: Calculate the Z-transform

   By definition, \( X(z) = \sum_{n=-\infty}^\infty δ[n] z^{-n} = z^{0} = 1 \).

3. Final Answer:

   X(z) = 1 -> Option D

4. Quick Check:

   Impulse Z-transform = 1 [OK]

Hint: Impulse transforms to 1 always [OK]

Common Mistakes:

• Confusing impulse with step function
• Adding z terms unnecessarily
• Forgetting impulse is zero except at n=0

3. What is the Z-transform of the sequence x[n] = n u[n]?

medium

A. X(z) = z^{-1} / (1 - z^{-1})^2, |z| > 1

B. X(z) = 1 / (1 - z^{-1})^2, |z| > 1

C. X(z) = z / (z - 1), |z| > 1

D. X(z) = 1 / (1 - z)^2, |z| > 1

Solution

1. Step 1: Recall the Z-transform of the sequence n u[n]

   The sequence n u[n] has Z-transform \( X(z) = \frac{z^{-1}}{(1 - z^{-1})^2} \) with region of convergence \( |z| > 1 \).

2. Step 2: Match the formula with the options

   X(z) = z^{-1} / (1 - z^{-1})^2, |z| > 1 matches the formula exactly including the region of convergence.

3. Final Answer:

   X(z) = z^{-1} / (1 - z^{-1})^2, |z| > 1 -> Option A

4. Quick Check:

   Linear sequence Z-transform = z^{-1}/(1 - z^{-1})^2 [OK]

Hint: Linear sequences transform to z^{-1}/(1 - z^{-1})^2 [OK]

Common Mistakes:

• Confusing powers of z
• Using (z - 1) instead of (1 - z^{-1})
• Ignoring region of convergence

4. Identify the error in the following Z-transform expression for x[n] = a^n u[n]: X(z) = 1 / (1 - z a^{-1})

medium

A. The variable z and a are swapped in the denominator

B. The region of convergence is missing

C. The exponent on a should be negative

D. The formula is correct as is

Solution

1. Step 1: Recall the correct Z-transform formula for a^n u[n]

   The correct formula is \( X(z) = \frac{1}{1 - a z^{-1}} \), not \( 1/(1 - z a^{-1}) \).

2. Step 2: Analyze the given expression

   The given expression swaps z and a in the denominator, which changes the meaning and is incorrect.

3. Final Answer:

   The variable z and a are swapped in the denominator -> Option A

4. Quick Check:

   Correct formula uses a z^{-1}, not z a^{-1} [OK]

Hint: Check order of variables in denominator carefully [OK]

Common Mistakes:

• Swapping z and a in denominator
• Ignoring negative powers of z
• Missing region of convergence

5. Given the sequence x[n] = (1/2)^n u[n] + 3 δ[n], what is the combined Z-transform X(z)?

hard

A. X(z) = 3 * z / (z - 1/2), |z| > 1/2

B. X(z) = 3 z^{-1} + 1 / (1 - (1/2) z^{-1}), |z| > 1/2

C. X(z) = 3 + 1 / (1 - (1/2) z^{-1}), |z| > 1/2

D. X(z) = 3 + 1 / (1 - 2 z^{-1}), |z| > 2

Solution

1. Step 1: Find Z-transform of each sequence part

   The Z-transform of (1/2)^n u[n] is \( \frac{1}{1 - (1/2) z^{-1}} \) with \( |z| > 1/2 \). The Z-transform of 3 δ[n] is 3.

2. Step 2: Add the transforms for combined sequence

   Since Z-transform is linear, add both: \( X(z) = 3 + \frac{1}{1 - (1/2) z^{-1}} \).

3. Final Answer:

   X(z) = 3 + 1 / (1 - (1/2) z^{-1}), |z| > 1/2 -> Option C

4. Quick Check:

   Sum of transforms = 3 + 1/(1 - 0.5 z^{-1}) [OK]

Hint: Sum transforms for combined sequences linearly [OK]

Common Mistakes:

• Multiplying instead of adding transforms
• Incorrect region of convergence
• Wrong coefficient placement