Q3 20 points The convolution C of two arrays of integers A a

Q3. (20 points) 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.

Solution

int[] CalculateConvolution(int[] A, int[] B, int N)
{
   int[N] C;
  
   for(int i=0; i<N; i++)
   {
       C[i] = 0;
       for(int j=0; j<N; j++)
       {
           if(i==0 && j==0)
           {
               C[i] += A[0]*B[0];
           }
           else
           {
               C[i] += A[j]*B[N-j];
           }
       }
   }
  
   return C;
}