Time scaling (compression and expansion) in Signal Processing - Time & Space Complexity

Time Complexity: Time scaling (compression and expansion)

O(n / s)

Understanding Time Complexity

We want to understand how the time it takes to process a signal changes when we speed it up or slow it down.

How does the work grow when we change the length of the signal by compressing or expanding it?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    def time_scale(signal, scale_factor):
        scaled_signal = []
        for i in range(int(len(signal) / scale_factor)):
            index = int(i * scale_factor)
            scaled_signal.append(signal[index])
        return scaled_signal
    

This code changes the speed of a signal by picking samples at intervals based on the scale factor.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the scaled signal length and accessing elements from the original signal.
• How many times: Approximately the length of the original signal divided by the scale factor.

How Execution Grows With Input

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

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

Pattern observation: The work grows linearly with the input size but is reduced by the scale factor.

Final Time Complexity

Time Complexity: O(n / s)

This means the time to process the signal grows linearly with the input length, adjusted by how much we compress or expand it.

Common Mistake

[X] Wrong: "Time scaling always takes the same time regardless of the scale factor."

[OK] Correct: Because the loop runs fewer or more times depending on how much the signal is compressed or expanded, the time changes with the scale factor.

Interview Connect

Understanding how time changes with signal length and scaling helps you explain performance in real signal processing tasks clearly and confidently.

Self-Check

"What if we used interpolation to fill in values instead of just picking samples? How would the time complexity change?"

Practice

1. What happens to a signal when it is time-scaled with a factor a > 1?

easy

A. The signal is expanded and plays slower.

B. The signal amplitude increases.

C. The signal is compressed and plays faster.

D. The signal frequency decreases.

Solution

1. Step 1: Understand time scaling factor meaning

   A factor a > 1 means the time axis is divided by a number greater than 1, making the signal shorter in time.

2. Step 2: Effect on signal playback speed

   Shorter time means the signal plays faster, which is called compression.

3. Final Answer:

   The signal is compressed and plays faster. -> Option C

4. Quick Check:

   Compression (a > 1) = Faster playback [OK]

Hint: If a > 1, signal speeds up (compresses) [OK]

Common Mistakes:

• Confusing compression with expansion
• Thinking amplitude changes with time scaling
• Mixing frequency effects with time scaling

2. Which of the following Python code snippets correctly applies time scaling by a factor a to a signal array x using interpolation?

easy

A. import numpy as np
n = len(x)
t = np.arange(n)
t_new = t / a
x_new = x[t_new]

B. import numpy as np
n = len(x)
t = np.arange(n)
t_new = t * a
x_new = x[t_new]

C. import numpy as np
from scipy.interpolate import interp1d
n = len(x)
t = np.arange(n)
f = interp1d(t, x)
t_new = t * a
x_new = f(t_new)

D. import numpy as np
from scipy.interpolate import interp1d
n = len(x)
t = np.arange(n)
f = interp1d(t, x)
t_new = t / a
x_new = f(t_new)

Solution

1. Step 1: Understand time scaling formula

   Time scaling by factor a means new time points are t_new = t / a.

2. Step 2: Use interpolation for non-integer indices

   Since t_new may be fractional, interpolation function f is used to get x_new.

3. Final Answer:

   Code snippet A correctly applies time scaling with interpolation. -> Option D

4. Quick Check:

   t_new = t / a with interp1d = Correct scaling [OK]

Hint: Use t_new = t / a with interpolation function [OK]

Common Mistakes:

• Multiplying time by a instead of dividing
• Indexing array directly with fractional indices
• Forgetting to import interp1d

3. Given the code below, what is the length of the output signal x_scaled?

import numpy as np
from scipy.interpolate import interp1d
x = np.array([1, 2, 3, 4, 5])
a = 0.5
n = len(x)
t = np.arange(n)
f = interp1d(t, x, kind='linear', fill_value='extrapolate')
t_new = t / a
x_scaled = f(t_new)

medium

A. 5

B. 10

C. 3

D. 7

Solution

1. Step 1: Check length of t_new

   Variable t_new is computed as t / a, but t has length 5, so t_new also has length 5.

2. Step 2: Interpolation output length

   Interpolating at 5 points returns an array x_scaled of length 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Length of t_new = length of x_scaled = 5 [OK]

Hint: Output length matches length of t_new array [OK]

Common Mistakes:

• Assuming output length changes with scaling factor
• Confusing scaling factor with output size
• Ignoring that t_new length equals original length

4. Identify the error in the following code that attempts to expand a signal by a factor of 2:

import numpy as np
from scipy.interpolate import interp1d
x = np.array([10, 20, 30, 40])
a = 2
n = len(x)
t = np.arange(n)
f = interp1d(t, x)
t_new = t * a
x_expanded = f(t_new)

medium

A. Using integer array t instead of float array.

B. Using t * a instead of t / a for time scaling.

C. Using interp1d without sorting t.

D. Not specifying fill_value in interp1d causes error.

Solution

1. Step 1: Recall time scaling formula

   To expand (slow down) a signal by factor 2, new time points should be t_new = t / a, not t * a.

2. Step 2: Effect of incorrect scaling

   Using t * a compresses the signal instead of expanding it, causing wrong output.

3. Final Answer:

   Using t * a instead of t / a for time scaling. -> Option B

4. Quick Check:

   Expansion requires t_new = t / a [OK]

Hint: Use t_new = t / a for expansion, not t * a [OK]

Common Mistakes:

• Multiplying time by a instead of dividing
• Ignoring interpolation domain limits
• Not handling extrapolation in interp1d

5. You have a signal sampled at 1000 Hz with 1000 samples. You want to create a time-scaled version that plays twice as slow (expansion). Which of the following code snippets correctly computes the new signal x_expanded with proper interpolation and new sampling points?

hard

A. import numpy as np
from scipy.interpolate import interp1d
x = original_signal
fs = 1000
n = len(x)
t = np.arange(n) / fs
f = interp1d(t, x, kind='cubic', fill_value='extrapolate')
t_new = np.arange(0, t[-1]*2, 1/fs)
x_expanded = f(t_new)

B. import numpy as np
from scipy.interpolate import interp1d
x = original_signal
fs = 1000
n = len(x)
t = np.arange(n) / fs
f = interp1d(t, x, kind='linear')
t_new = np.arange(0, t[-1]/2, 1/fs)
x_expanded = f(t_new)

C. import numpy as np
from scipy.interpolate import interp1d
x = original_signal
fs = 1000
n = len(x)
t = np.arange(n) / fs
f = interp1d(t, x)
t_new = np.arange(0, t[-1]*2, 2/fs)
x_expanded = f(t_new)

D. import numpy as np
from scipy.interpolate import interp1d
x = original_signal
fs = 1000
n = len(x)
t = np.arange(n) / fs
f = interp1d(t, x, kind='cubic')
t_new = np.arange(0, t[-1]*0.5, 1/fs)
x_expanded = f(t_new)

Solution

1. Step 1: Understand expansion by factor 2

   Playing twice as slow means the signal duration doubles, so new time axis goes from 0 to t[-1]*2.

2. Step 2: Create new time points at original sampling rate

   New time points should be spaced by 1/fs to keep sampling rate consistent.

3. Step 3: Use interpolation with extrapolation

   Interpolation function with cubic method and fill_value='extrapolate' handles points beyond original range.

4. Final Answer:

   Code snippet A correctly computes the expanded signal. -> Option A

5. Quick Check:

   Expansion doubles duration with proper interpolation [OK]

Hint: Double time axis length, keep sampling interval, interpolate [OK]

Common Mistakes:

• Reducing time axis length instead of expanding
• Changing sampling interval incorrectly
• Not handling extrapolation in interpolation