Rectangular window limitations in Signal Processing - Time & Space Complexity

Time Complexity: Rectangular window limitations

O(n)

Understanding Time Complexity

We want to understand how the time needed to apply a rectangular window changes as the input signal gets longer.

How does the processing time grow when we increase the signal size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def apply_rectangular_window(signal):
    N = len(signal)
    windowed_signal = []
    for i in range(N):
        windowed_signal.append(signal[i] * 1)  # Rectangular window multiplies by 1
    return windowed_signal
    

This code multiplies each element of the input signal by 1, which is the rectangular window operation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each element of the signal to multiply by 1.
• How many times: Exactly once for each element, so N times where N is the signal length.

How Execution Grows With Input

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

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

Pattern observation: The operations increase directly in proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to apply the rectangular window grows linearly with the signal length.

Common Mistake

[X] Wrong: "Applying a rectangular window is instant and does not depend on signal size."

[OK] Correct: Even though the window multiplies by 1, the code still processes each element, so time grows with signal length.

Interview Connect

Understanding how simple windowing operations scale helps you reason about signal processing efficiency in real tasks.

Self-Check

"What if we changed the rectangular window to a Hamming window that requires different multiplications for each element? How would the time complexity change?"