Provide the best algorithm for all the problems below using c++. Write their run

Question

Provide the best algorithm for all the problems below using c++. Write their running time functions using Big-O notation.

(a) Find the inner product of two vectors v1 and v2, each of size n.
(b) Find the number of occurrences of an element t in a vector/array v, of size n.

(c) Concatenate two strings, each of n characters long.

(d) Remove the i-th element from a vector/array

(e) Find in a vector/array the sum of only those elements which are less than 43.

(f) Add an element to the beginning/end of a vector/array v.

Explanation / Answer

(a)

double innerProduct(vector<double> v1, vector<double> v2){

   double ans = 0;
   for(int i = 0; i < n; i++){
       ans += v1[i] * v2[i];
   }
   return ans;
}

// Complexity: O(n)

(b)

double innerProduct(int v[], int n, int t){
   double count = 0;
   for(int i = 0; i < n; i++){
       if(v[i] == t) count++;
   }
   return count;
}

// Complexity: O(n)

(c)

void append(char a[], char b[], int n){
   for(i = 0; a[i] != ''; i++);
for(j = 0; b[j] != ''; j++, i++){
s1[i] = s2[j];
}
s1[i] = '';
}

// Complexity: O(n)

(d)

void removeIth(int arr[], int n, int i){
   for(int j = i; j < n - 1; j++){
       arr[j] = arr[j + 1];
   }
   n--;
}

// Complexity = O(n)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.