Time shifting a signal in Signal Processing - Time & Space Complexity

Time Complexity: Time shifting a signal

O(n)

Understanding Time Complexity

We want to understand how the time it takes to shift a signal changes as the signal gets longer.

How does the work grow when we move the signal in time?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Shift a signal by k samples
shifted_signal = [0]*len(signal)
for i in range(len(signal)):
    if 0 <= i - k < len(signal):
        shifted_signal[i] = signal[i - k]
    else:
        shifted_signal[i] = 0

This code moves the signal by k steps, filling empty spots with zeros.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element of the signal array.
• How many times: Exactly once for every element in the signal.

How Execution Grows With Input

As the signal length grows, the number of steps grows the same way.

Input Size (n)	Approx. Operations
10	10
100	100
1000	1000

Pattern observation: Doubling the signal length doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to shift the signal grows directly with the signal length.

Common Mistake

[X] Wrong: "Shifting a signal takes constant time because we just move it once."

[OK] Correct: Each element must be moved or assigned, so the work depends on the signal size, not just one step.

Interview Connect

Understanding how simple operations like shifting scale helps you explain your code clearly and shows you know how to think about efficiency.

Self-Check

"What if we shifted the signal multiple times in a row? How would the time complexity change?"

Practice

1. What does a positive time shift do to a signal in signal processing?

easy

A. It advances the signal, moving it backward in time.

B. It delays the signal, moving it forward in time.

C. It changes the signal's amplitude.

D. It reverses the signal in time.

Solution

1. Step 1: Understand time shift direction

   A positive time shift means the signal is moved to a later time, which delays it.

2. Step 2: Compare options with definition

   Only It delays the signal, moving it forward in time. correctly states that a positive shift delays the signal.

3. Final Answer:

   It delays the signal, moving it forward in time. -> Option B

4. Quick Check:

   Positive shift = delay [OK]

Hint: Positive shift means delay, negative means advance [OK]

Common Mistakes:

• Confusing positive shift with advancing the signal
• Thinking time shift changes amplitude
• Mixing up delay and reversal

2. Which of the following is the correct Python syntax to shift a discrete signal array x by 3 units forward (delay)?

easy

A. shifted_x = np.roll(x, 3)

B. shifted_x = np.roll(x, -3)

C. shifted_x = x + 3

D. shifted_x = x.shift(3)

Solution

1. Step 1: Understand np.roll behavior

   In numpy, np.roll(x, 3) shifts elements to the right by 3, delaying the signal.

2. Step 2: Check other options

   shifted_x = x.shift(3) is invalid syntax for numpy arrays, np.roll(x, -3) shifts left (advances), x + 3 adds 3 to values (not time shift).

3. Final Answer:

   shifted_x = np.roll(x, 3) -> Option A

4. Quick Check:

   np.roll with positive shift delays signal [OK]

Hint: np.roll with positive number delays signal [OK]

Common Mistakes:

• Using negative shift to delay signal
• Adding number to array instead of rolling
• Using non-existent shift method

3. Given the signal array x = [1, 2, 3, 4, 5], what is the output of np.roll(x, -2)?

medium

A. [4, 5, 1, 2, 3]

B. [2, 3, 4, 5, 1]

C. [3, 4, 5, 1, 2]

D. [5, 1, 2, 3, 4]

Solution

1. Step 1: Understand np.roll with negative shift

   Negative shift moves elements to the left by 2 positions.

2. Step 2: Apply shift to array

   Original: [1, 2, 3, 4, 5]
   Shift left 2: [3, 4, 5, 1, 2]

3. Final Answer:

   [3, 4, 5, 1, 2] -> Option C

4. Quick Check:

   Negative shift = advance signal [OK]

Hint: Negative np.roll shifts left (advances) [OK]

Common Mistakes:

• Confusing left and right shift directions
• Miscounting shifted elements
• Assuming shift changes values

4. The following code attempts to shift a signal x = [10, 20, 30, 40] by 1 unit forward but produces incorrect output. What is the error?

shifted_x = np.roll(x, -1)

medium

A. The shift value should be positive to delay the signal.

B. np.roll cannot be used for shifting signals.

C. The array x must be converted to a numpy array first.

D. The shift value should be zero for no change.

Solution

1. Step 1: Analyze shift direction

   Negative shift (-1) moves signal left (advances), not forward (delay).

2. Step 2: Correct shift value

   To delay (shift forward), use positive shift value +1.

3. Final Answer:

   The shift value should be positive to delay the signal. -> Option A

4. Quick Check:

   Positive shift delays signal [OK]

Hint: Positive shift delays; negative advances [OK]

Common Mistakes:

• Using negative shift to delay signal
• Thinking np.roll is invalid for shifting
• Forgetting to convert list to numpy array (not required here)

5. You have two signals sampled at the same rate: s1 = [0, 1, 2, 3, 4] and s2 = [3, 4, 0, 1, 2]. Which time shift applied to s1 aligns it best with s2?

hard

A. Shift s1 by +3 units (delay by 3)

B. Shift s1 by +1 units (delay by 1)

C. Shift s1 by -2 units (advance by 2)

D. Shift s1 by -3 units (advance by 3)

Solution

1. Step 1: Compare signals visually

   s1 = [0, 1, 2, 3, 4], s2 = [3, 4, 0, 1, 2]. s2 matches s1 advanced (shifted left) by 3.

2. Step 2: Verify with np.roll

   np.roll(s1, -3) = [3, 4, 0, 1, 2] matches s2 exactly. np.roll(s1, 1) = [4, 0, 1, 2, 3], np.roll(s1, -2) = [2, 3, 4, 0, 1], np.roll(s1, 3) = [2, 3, 4, 0, 1] do not match.

3. Final Answer:

   Shift s1 by -3 units (advance by 3) -> Option D

4. Quick Check:

   np.roll(s1, -3) == s2 [OK]

Hint: Match s2 by rolling s1 left/right to align [OK]

Common Mistakes:

• Choosing wrong shift direction
• Not checking exact element alignment
• Confusing delay with advance