Convolution in MATLAB - Time & Space Complexity

Time Complexity: Convolution

O(n * m)

Understanding Time Complexity

We want to understand how the time it takes to perform convolution changes as the input size grows.

How does the number of calculations grow when we convolve two signals of different lengths?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

% Simple convolution of two vectors x and h
x = rand(1, n);       % Input signal of length n
h = rand(1, m);       % Filter of length m

y = zeros(1, n+m-1);  % Output vector
for i = 1 : n+m-1
    for j = 1 : m
        if (i - j + 1 >= 1) && (i - j + 1 <= n)
            y(i) = y(i) + x(i - j + 1) * h(j);
        end
    end
end
    

This code calculates the convolution of two vectors by sliding one over the other and summing products.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops multiplying and summing elements of x and h.
• How many times: Outer loop runs about n+m times, inner loop runs m times each time.

How Execution Grows With Input

As the input size n grows, the total operations grow roughly by n times m.

Input Size (n)	Approx. Operations
10	About 10 x m
100	About 100 x m
1000	About 1000 x m

Pattern observation: The work grows linearly with the length of the input signal and the filter size.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to compute convolution grows proportionally to the product of the input and filter lengths.

Common Mistake

[X] Wrong: "Convolution always takes the same time regardless of input size."

[OK] Correct: The number of calculations depends on how long the input and filter are; bigger inputs mean more work.

Interview Connect

Understanding how convolution scales helps you explain performance in signal processing or image tasks, showing you grasp how algorithms behave with bigger data.

Self-Check

"What if we used a filter of fixed size regardless of input length? How would the time complexity change?"

Practice

1. What does the MATLAB function conv(x, h) compute?

easy

A. The convolution of vectors x and h

B. The element-wise multiplication of x and h

C. The dot product of x and h

D. The sum of vectors x and h

Solution

1. Step 1: Understand the function purpose

   The conv function in MATLAB is designed to compute the convolution of two vectors.

2. Step 2: Differentiate convolution from other operations

   Convolution combines two signals to produce a third, different from element-wise multiplication, dot product, or sum.

3. Final Answer:

   The convolution of vectors x and h -> Option A

4. Quick Check:

   conv(x, h) = convolution [OK]

Hint: Remember conv() means convolution, not multiplication [OK]

Common Mistakes:

• Confusing convolution with element-wise multiplication
• Thinking conv() sums vectors
• Mixing up dot product with convolution

2. Which of the following is the correct syntax to compute convolution of vectors a and b in MATLAB?

easy

A. conv(a, b)

B. convolve(a, b)

C. a * b

D. conv(a + b)

Solution

1. Step 1: Recall MATLAB convolution syntax

   MATLAB uses the function conv(x, h) to compute convolution of two vectors.

2. Step 2: Check each option

   conv(a, b) matches the correct syntax. convolve(a, b) is not a MATLAB function. a * b is matrix multiplication, not convolution. conv(a + b) has wrong argument format.

3. Final Answer:

   conv(a, b) -> Option A

4. Quick Check:

   Use conv(x, h) syntax [OK]

Hint: Use conv() with two arguments separated by comma [OK]

Common Mistakes:

• Using non-existent function convolve()
• Trying to multiply vectors with * for convolution
• Passing only one argument to conv()

3. What is the length of the output vector when you compute conv([1 2 3], [4 5]) in MATLAB?

medium

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Identify lengths of input vectors

   Vector [1 2 3] has length 3, and [4 5] has length 2.

2. Step 2: Calculate output length of convolution

   Output length = length(x) + length(h) - 1 = 3 + 2 - 1 = 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Output length = 3 + 2 - 1 = 4 [OK]

Hint: Output length = sum of input lengths minus one [OK]

Common Mistakes:

• Assuming output length equals input length
• Adding lengths without subtracting one
• Confusing convolution length with element-wise length

4. Consider the MATLAB code:

a = [1 2]; b = [3 4 5]; c = conv(a b);

What is the error in this code?

medium

A. Vectors a and b have different lengths

B. Missing comma between a and b in conv function

C. conv function does not exist in MATLAB

D. Using square brackets instead of parentheses

Solution

1. Step 1: Check syntax of conv function call

   The function call conv(a b) is missing a comma between the two input vectors.

2. Step 2: Verify other options

   Vectors can have different lengths for convolution. conv() is a valid MATLAB function. Square brackets are used correctly for vector definition, not in function call.

3. Final Answer:

   Missing comma between a and b in conv function -> Option B

4. Quick Check:

   Use comma to separate arguments in conv() [OK]

Hint: Separate arguments with comma inside conv() [OK]

Common Mistakes:

• Omitting comma between function arguments
• Thinking vectors must be same length
• Confusing vector definition brackets with function call syntax

5. You want to convolve two signals x = [1 0 2] and h = [3 4] but only keep the output length equal to the length of x. Which MATLAB command achieves this?

hard

A. conv(x, h, 'full')

B. conv(x, h)

C. conv(x, h, 'same')

D. conv(x, h, 'valid')

Solution

1. Step 1: Understand convolution output length options

   By default, conv(x, h) returns full convolution with length length(x)+length(h)-1.

2. Step 2: Use 'same' option to keep output length equal to x

   Using conv(x, h, 'same') returns the central part of the convolution, matching length of x.

3. Final Answer:

   conv(x, h, 'same') -> Option C

4. Quick Check:

   'same' option keeps output length equal to first input [OK]

Hint: Use 'same' option in conv() to match input length [OK]

Common Mistakes:

• Using default conv() which returns longer output
• Confusing 'valid' and 'same' options
• Expecting conv() to truncate output automatically