Even and odd signal decomposition in Signal Processing - Time & Space Complexity

Time Complexity: Even and odd signal decomposition

O(n)

Understanding Time Complexity

We want to understand how the time needed to split a signal into even and odd parts changes as the signal gets longer.

How does the work grow when the signal size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for n in range(len(x)):
    x_even[n] = (x[n] + x[-n-1]) / 2
    x_odd[n] = (x[n] - x[-n-1]) / 2
    

This code splits a signal x into its even and odd parts by combining values from opposite ends.

Identify Repeating Operations

• Primary operation: A single loop that goes through each element of the signal.
• How many times: The loop runs once for every element in the signal, so n times if the signal length is n.

How Execution Grows With Input

As the signal gets longer, the number of steps grows directly with the length.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to split the signal grows in a straight line with the signal length.

Common Mistake

[X] Wrong: "Because we access x[-n], the code does extra work and is slower than linear."

[OK] Correct: Accessing x[-n] is just another index lookup and does not add extra loops or nested work. It still happens once per element.

Interview Connect

Understanding how simple loops scale helps you explain your code clearly and shows you know how to reason about performance in signal processing tasks.

Self-Check

"What if we decomposed the signal using nested loops comparing every pair of points? How would the time complexity change?"

Practice

1.

What is the main property of an even signal x(t) in signal processing?

easy

A. It satisfies x(t) = -x(-t) for all t.

B. It has no negative values.

C. It is always zero at t=0.

D. It satisfies x(t) = x(-t) for all t.

Solution

1. Step 1: Recall definition of even signal

   An even signal is symmetric about zero, meaning the value at t equals the value at -t.

2. Step 2: Apply the property to the signal

   This means x(t) = x(-t) for every time t.

3. Final Answer:

   It satisfies x(t) = x(-t) for all t. -> Option D

4. Quick Check:

   Even signal = x(t) = x(-t) [OK]

Hint: Even signals mirror values at positive and negative times [OK]

Common Mistakes:

• Confusing even with odd signal definitions
• Thinking even signals must be zero at t=0
• Assuming even signals cannot have negative values

2.

Which of the following is the correct formula to find the odd part x_o(t) of a signal x(t)?

easy

A. x_o(t) = (x(t) + x(-t)) / 2

B. x_o(t) = (x(t) - x(-t)) / 2

C. x_o(t) = x(t) * x(-t)

D. x_o(t) = x(t) / x(-t)

Solution

1. Step 1: Recall formula for odd part of a signal

   The odd part is defined as half the difference between the signal and its time-reversed version: x_o(t) = (x(t) - x(-t)) / 2.

2. Step 2: Verify the formula matches the odd signal property

   This formula ensures x_o(-t) = -x_o(t), which is the odd signal condition.

3. Final Answer:

   x_o(t) = (x(t) - x(-t)) / 2 -> Option B

4. Quick Check:

   Odd part = (x(t) - x(-t))/2 [OK]

Hint: Odd part uses subtraction of reversed signal, then divide by 2 [OK]

Common Mistakes:

• Using addition instead of subtraction for odd part
• Multiplying signals instead of subtracting
• Dividing by wrong number or not dividing at all

3.

Given a discrete signal x = [2, 3, 4, 3, 2] indexed from -2 to 2, what is the even part x_e of this signal?

Use the formula x_e[n] = (x[n] + x[-n]) / 2.

medium

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

B. [2, 3.5, 4, 3.5, 2]

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

D. [2, 3.5, 4, 3, 2]

Solution

1. Step 1: Identify signal values and indices

   Signal x indexed from -2 to 2 is: x[-2]=2, x[-1]=3, x[0]=4, x[1]=3, x[2]=2.

2. Step 2: Calculate even part using formula

   Calculate each x_e[n] = (x[n] + x[-n]) / 2: - n=-2: (x[-2]+x[2])/2 = (2+2)/2=2 - n=-1: (x[-1]+x[1])/2 = (3+3)/2=3 - n=0: (x[0]+x[0])/2 = (4+4)/2=4 - n=1: (x[1]+x[-1])/2 = (3+3)/2=3 - n=2: (x[2]+x[-2])/2 = (2+2)/2=2 But note the signal is symmetric, so values are same as original except at n=1 and n=-1 where average is 3.

3. Final Answer:

   [2, 3, 4, 3, 2] -> Option A

4. Quick Check:

   Even part averages signal and its mirror [OK]

Hint: Average signal values at n and -n for even part [OK]

Common Mistakes:

• Not averaging values correctly
• Mixing indices n and -n
• Using odd part formula instead

4.

Consider the Python code below to compute the odd part of a signal x:

def odd_part(x):
    return [(x[i] - x[-i]) / 2 for i in range(len(x))]

What is the main error in this code?

medium

A. The range should start from 1, not 0.

B. The formula uses addition instead of subtraction.

C. Indexing with negative indices -i is incorrect for this context.

D. The division by 2 is missing.

Solution

1. Step 1: Understand indexing in Python lists

   Python negative indices count from the end, so -i does not correspond to -n time index but to list end positions.

2. Step 2: Identify correct indexing for signal symmetry

   For signal indexed from negative to positive, indexing must map i to -i properly, which this code does not do because list indices are 0-based and -i accesses wrong elements.

3. Final Answer:

   Indexing with negative indices -i is incorrect for this context. -> Option C

4. Quick Check:

   Python negative indices ≠ signal negative time [OK]

Hint: Python negative indices count from list end, not negative time [OK]

Common Mistakes:

• Assuming -i indexes negative time correctly
• Ignoring zero-based indexing
• Confusing addition/subtraction in formula

5.

You have a signal x(t) = t^3 + 2t. Decompose it into even and odd parts. What is the even part x_e(t)?

hard

A. x_e(t) = 0

B. x_e(t) = t^3

C. x_e(t) = 2t

D. x_e(t) = t^3 + 2t

Solution

1. Step 1: Identify even and odd nature of terms

   The term t^3 is an odd function because (-t)^3 = -t^3. The term 2t is also odd because 2(-t) = -2t.

2. Step 2: Calculate even part using formula

   Even part is x_e(t) = (x(t) + x(-t)) / 2. Substitute: x_e(t) = (t^3 + 2t + (-t)^3 + 2(-t)) / 2 = (t^3 + 2t - t^3 - 2t) / 2 = 0.

3. Final Answer:

   x_e(t) = 0 -> Option A

4. Quick Check:

   Sum of odd functions is odd, so even part is zero [OK]

Hint: Sum of odd functions has zero even part [OK]

Common Mistakes:

• Assuming polynomial terms are even by default
• Mixing odd and even function properties
• Forgetting to apply formula correctly