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?"

Practice

1. What is a main limitation of using a rectangular window in signal processing?

easy

A. It causes frequency spreading and high side lobes

B. It completely removes noise from the signal

C. It increases the signal amplitude

D. It shortens the signal duration

Solution

1. Step 1: Understand the rectangular window effect

   The rectangular window is a simple window that cuts the signal abruptly, causing spectral leakage.

2. Step 2: Identify the impact on frequency analysis

   This abrupt cut causes frequency spreading and high side lobes, making it hard to distinguish close frequencies.

3. Final Answer:

   It causes frequency spreading and high side lobes -> Option A

4. Quick Check:

   Rectangular window = frequency spreading and side lobes [OK]

Hint: Rectangular window causes side lobes and spreading [OK]

Common Mistakes:

• Thinking it removes noise completely
• Believing it increases signal amplitude
• Assuming it shortens signal duration

2. Which of the following is the correct way to apply a rectangular window to a signal array sig in Python using NumPy?

easy

A. windowed = sig + np.zeros(len(sig))

B. windowed = sig * np.ones(len(sig))

C. windowed = sig / np.ones(len(sig))

D. windowed = sig - np.ones(len(sig))

Solution

1. Step 1: Recall rectangular window definition

   A rectangular window is an array of ones with the same length as the signal.

2. Step 2: Apply window by element-wise multiplication

   Multiplying the signal by an array of ones keeps the signal unchanged but applies the window.

3. Final Answer:

   windowed = sig * np.ones(len(sig)) -> Option B

4. Quick Check:

   Rectangular window = multiply by ones array [OK]

Hint: Multiply signal by ones array for rectangular window [OK]

Common Mistakes:

• Adding or subtracting ones instead of multiplying
• Dividing by ones which is unnecessary
• Using zeros which nullifies the signal

3. Given the following Python code, what will be the approximate side lobe level in dB when using a rectangular window on a signal?

import numpy as np
N = 64
rect_win = np.ones(N)
# Side lobe level for rectangular window is about -13 dB

medium

A. -3 dB

B. -60 dB

C. -40 dB

D. -13 dB

Solution

1. Step 1: Recall typical side lobe level for rectangular window

   The rectangular window has a main lobe and side lobes around -13 dB relative to the main lobe.

2. Step 2: Match the known value to options

   Among the options, -13 dB matches the known side lobe level for rectangular windows.

3. Final Answer:

   -13 dB -> Option D

4. Quick Check:

   Rectangular window side lobes ≈ -13 dB [OK]

Hint: Rectangular window side lobes near -13 dB [OK]

Common Mistakes:

• Confusing side lobe level with main lobe width
• Choosing much lower side lobe levels like -40 dB
• Assuming side lobes are negligible

4. You have this code snippet to apply a rectangular window but it causes unexpected frequency leakage:

import numpy as np
signal = np.sin(2 * np.pi * 5 * np.arange(100) / 100)
window = np.ones(50)
windowed_signal = signal * window

What is the main error?

medium

A. Window length does not match signal length

B. Window contains zeros instead of ones

C. Signal frequency is too high for window

D. Multiplication should be addition

Solution

1. Step 1: Check window and signal length

   The signal length is 100, but the window length is only 50, causing a length mismatch.

2. Step 2: Understand effect of length mismatch

   Multiplying arrays of different lengths causes broadcasting or unintended results, leading to frequency leakage.

3. Final Answer:

   Window length does not match signal length -> Option A

4. Quick Check:

   Window length must equal signal length [OK]

Hint: Window length must match signal length [OK]

Common Mistakes:

• Ignoring length mismatch
• Thinking zeros in window cause leakage
• Confusing multiplication with addition

5. You want to analyze two close frequencies in a signal but the rectangular window causes them to blur together. Which approach best reduces this limitation?

hard

A. Apply rectangular window twice in a row

B. Increase the signal amplitude before applying rectangular window

C. Use a window with lower side lobes like Hamming or Hann

D. Shorten the signal length to reduce frequency resolution

Solution

1. Step 1: Identify the problem with rectangular window

   Rectangular window has high side lobes causing frequency spreading, blurring close frequencies.

2. Step 2: Choose a better window to reduce side lobes

   Windows like Hamming or Hann have lower side lobes, improving frequency resolution and reducing blur.

3. Final Answer:

   Use a window with lower side lobes like Hamming or Hann -> Option C

4. Quick Check:

   Lower side lobes = clearer frequency separation [OK]

Hint: Choose low side lobe windows to separate close frequencies [OK]

Common Mistakes:

• Increasing amplitude does not fix side lobes
• Shortening signal reduces resolution, worsening problem
• Applying rectangular window twice has no benefit