Question

The convolution C of two arrays of integers A and B, where A and B are of size n, is defined as follows:

C[k] = ∑ A[i] *B[j]

where the sum is over all possible values of i and j such that k=( i+j) mod n , and i,j,k= 0,1,2……n-1.

For example if n=3, C[0]= A[0]*B[0]+ A[1]*B[2] +A[2]*B[1] C[1]= A[0]*B[1] + A[1]*B[0] + A[2]*B[2] C[2]= A[0]*B[2] + A[1]*B[1] + A[2]*B[0]

Write an algorithm with quadratic time complexity for computing C.

Answer 1

So, basically we need to find array C.

So, for each element C[k] where 0 < k < n-1, we need to find i,j such that  k=( i + j ) mod n in O(n^2) time.

Algorithm:

For k in range(0,n):

find all pairs(i,j) such that k=( i + j ) mod n

So, note that outer loop run n times. And each time we can find pairs(i,j) such that k=( i + j ) mod n in O(n) time as follows:

• set initial value of i = 0 set initial value of j = k
• And then now each time increase the value of i by 1 and decrease the value of j by 1
• when j = 0, instead of assigning j = -1, assign j = n-1
• do consider duplicate pairs

So overall algorithm is O(n^2).